题解 P3268 【[JLOI2016]圆的异或并】
Leianha
·
·
题解
扫描线
博客阅读
之前做过一到类似的，当时没写题解，今天来补上。
首先我们发现圆没有交，所以两个圆只有包含和相离两种关系。
我们考虑用扫描线来处理，随着扫描线的推移，和上面的圆的交点 一直都在 和下面的圆的交点的上面，可以用 set 来维护相对位置
怎么确定一个圆应该是加还是减？我们将圆拆分成上半圆和下半圆，将上半圆插入 set 后，找在这扫描线上其下面的那个半圆。
$2$ .若是下半圆，则和那个圆的加减状态相反。
$3$ .若是上半圆，则和那个圆的加减状态相同。
上面的过程建议画一下图方便理解
```cpp
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<set>
#define DB double
using namespace std;
int n, tot, now;
long long ans;
DB nowx;
const int N = 200010;
const DB eps = 1e-9;
int val[N];
DB x[N], y[N], r[N];
struct cir
{
int opt, id;
DB nowy()//求圆和当前扫描线交点的y坐标
{
return y[id] + (DB)opt * sqrt(r[id] * r[id] - (x[id] - nowx) * (x[id] - nowx) + eps);
}
friend bool operator <(cir x, cir y) {return x.nowy() < y.nowy();}
};
set<cir>s;
set<cir>::iterator it;
struct xian
{
int opt, x, id;
friend bool operator <(const xian &x, const xian &y) {return x.x < y.x;}
} li[N << 1];
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i)
{
scanf("%lf%lf%lf", &x[i], &y[i], &r[i]);
li[++tot] = (xian) {1, (int)(x[i] - r[i]), i};
li[++tot] = (xian) {0, (int)(x[i] + r[i]), i};
}
sort(li + 1, li + 1 + tot);
for (int i = 1; i <= tot; ++i)
{
nowx = li[i].x;
if (li[i].opt)
{
now = li[i].id; it = s.insert((cir) {1, now}).first;
if (it == s.begin())val[now] = 1;
else
{
--it;
if ((*it).opt == -1)val[now] = val[(*it).id] ^ 1;
else val[now] = val[(*it).id];
}
s.insert((cir) { -1, now});
if (val[now])ans += r[now] * r[now];
else ans -= r[now] * r[now];
}
else s.erase((cir) {1, li[i].id}), s.erase((cir) { -1, li[i].id});
}
cout << ans;
return 0;
}
```