【BZOJ4561】[JLoi2016]圆的异或并
Description
在平面直角坐标系中给定N个圆。已知这些圆两两没有交点，即两圆的关系只存在相离和包含。求这些圆的异或面积并。异或面积并为：当一片区域在奇数个圆内则计算其面积，当一片区域在偶数个圆内则不考虑。
Input
第一行包含一个正整数N，代表圆的个数。接下来N行，每行3个非负整数x,y,r，表示一个圆心在(x,y)，半径为r的圆。保证|x|,|y|,≤10^8，r>0,N<=200000
Output
仅一行一个整数，表示所有圆的异或面积并除以圆周率Pi的结果。
Sample Input
2
0 0 1
0 0 2
0 0 1
0 0 2
Sample Output
3
题解：首先有一个非常重要的性质，由于所有圆不相交，所以任何时候所有圆的相对位置是不变的。
然后，我们对将个圆拆成加入和删除两个事件，左边加入右边删除。加入时相当于在set中加入了上下两个圆弧。然后用扫描线从左到右扫描，当加入一个圆时，在set中找到它外面的一层圆，则当前圆的符号=-外层圆的符号。特别地，如果我们在当前圆的上面找到了一个下半圆，则说明它和那个圆的关系是并列的，所以符号相同。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <cmath>
using namespace std;
const int maxn=200010;
typedef long long ll;
int n,now;
int x[maxn],y[maxn],r[maxn],f[maxn];
ll ans;
struct edgex
{
int v,k;
edgex() {}
edgex(int a,int b){v=a,k=b;} }p[maxn<<1];
bool operator < (edgex a,edgex b)
{
int pa=x[a.v]+a.k*r[a.v],pb=x[b.v]+b.k*r[b.v];
return pa<pb;
}
struct edgey
{
int v,k;
edgey() {}
edgey(int a,int b){v=a,k=b;}
double gety()
{
return y[v]+k*sqrt(1.0*r[v]*r[v]-1.0*(x[v]-now)*(x[v]-now));
}
};
bool operator < (edgey a,edgey b)
{
double ya=a.gety(),yb=b.gety();
if(fabs(ya-yb)<1e-7) return a.k<b.k;
return ya<yb;
}
set<edgey> s;
set<edgey>::iterator it;
int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
int main()
{
n=rd();
int i;
for(i=1;i<=n;i++) x[i]=rd(),y[i]=rd(),r[i]=rd(),p[i]=edgex(i,-1),p[i+n]=edgex(i,1);
sort(p+1,p+2*n+1);
for(i=1;i<=2*n;i++)
{
if(p[i].k==-1)
{
edgey t1(p[i].v,-1),t2(p[i].v,1);
it=s.upper_bound(t2);
if(it!=s.end()) f[p[i].v]=-f[(*it).v];
else f[p[i].v]=1;
s.insert(t1),s.insert(t2);
}
else s.erase(edgey(p[i].v,-1)),s.erase(edgey(p[i].v,1));
}
for(i=1;i<=n;i++) ans+=(ll)f[i]*r[i]*r[i];
printf("%lld",ans);
return 0;
}