Description
在平面直角坐标系中给定N个圆。已知这些圆两两没有交点，即两圆的关系只存在相离和包含。求这些圆的异或面
积并。异或面积并为：当一片区域在奇数个圆内则计算其面积，当一片区域在偶数个圆内则不考虑。
Input
第一行包含一个正整数N，代表圆的个数。接下来N行，每行3个非负整数x,y,r，表示一个圆心在(x,y)，半径为r的
圆。保证|x|,|y|,≤10^8，r>0,N<=200000
Output
仅一行一个整数，表示所有圆的异或面积并除以圆周率Pi的结果。
用平衡树维护扫描线与圆的交点
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<set>
typedef long long i64;
const int N=;
int n;
i64 xs[N],ys[N],rs[N],X;
inline i64 p2(i64 x){return x*x;}
inline int _int(){
int x=,c=getchar(),f=;
while(c>||c<){if(c=='-')f=-;c=getchar();}
while(c>&&c<)x=x*+c-,c=getchar();
return x*f;
}
struct pos{
i64 x,y;
int sgn,dep;
i64 r;
double Y(){
i64 a=r-p2(x-X);
if(a<)return y;
return y+sgn*sqrt(a);
}
};
bool operator<(pos a,pos b){
double x=a.Y(),y=b.Y();
if(fabs(x-y)>=.)return x<y;
return a.sgn<b.sgn;
}
struct event{
bool in;
int id;
i64 x(){
if(in)return xs[id]-rs[id];
else return xs[id]+rs[id];
}
}e[N*];
bool operator<(event a,event b){
i64 c=a.x(),d=b.x();
if(c!=d)return c<d;
return a.in<b.in;
}
std::set<pos>line;
int deps[N];
int xp;
i64 xv[N*];
int main(){
n=_int();
for(int i=;i<n;i++){
xs[i]=_int();ys[i]=_int();rs[i]=_int();
xv[i*]=(e[i*]=(event){,i}).x();
xv[i*+]=(e[i*+]=(event){,i}).x();
}
std::sort(e,e+n*);
for(int p=;p<n*;++p){
int id=e[p].id,d;
if(e[p].in){
X=e[p].x();
pos w=(pos){xs[id],ys[id],,,p2(rs[id])};
std::set<pos>::iterator it=line.upper_bound(w);
if(it!=line.end()){
w=*it;
d=(w.sgn==?-w.dep:w.dep);
}else d=;
line.insert((pos){xs[id],ys[id],,d,p2(rs[id])});
line.insert((pos){xs[id],ys[id],-,d,p2(rs[id])});
deps[id]=d;
}else{
X=e[p].x();
line.erase(line.find((pos){xs[id],ys[id],,,p2(rs[id])}));
line.erase(line.find((pos){xs[id],ys[id],-,,p2(rs[id])}));
}
}
i64 ans=;
for(int i=;i<n;i++)ans+=rs[i]*rs[i]*deps[i];
printf("%lld\n",ans);
return ;
}