[BZOJ4561][JLOI2016]圆的异或并(扫描线)

考虑任何一条垂直于x轴的直线，由于圆不交，所以这条直线上的圆弧构成形似括号序列的样子，且直线移动时圆之间的相对位置不变。

将每个圆拆成两边，左端加右端删。每次加圆时考虑它外面最内层的括号属于谁。用set维护括号序列，每次从插入的位置往上找，如果第一个找到的是上括弧则说明被它包含，如果是下括弧说明和它并列。这样每个圆的符号就可以确定了。

 #include<set>

 #include<cmath>

 #include<cstdio>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 typedef long long ll;

 using namespace std;

 const int N=;

 int n,tmp,f[N];

 ll ans,x[N],y[N],r[N];

 struct P{ int x,f,id; }q[N];

 double gety(int id,int p,int k)

 { return y[id]+k*sqrt(r[id]*r[id]-(x[id]-p)*(x[id]-p)); }

 struct D{ int id,k; };

 bool operator <(const D &a,const D &b){

     return (a.id==b.id) ? a.k<b.k : gety(a.id,tmp,a.k)<gety(b.id,tmp,b.k);

 }

 set<D> S;

 bool cmp(const P &a,const P &b){ return a.x==b.x ? a.f<b.f : a.x<b.x; }

 int main(){

     freopen("bzoj4561.in","r",stdin);

     freopen("bzoj4561.out","w",stdout);

     scanf("%d",&n);

     rep(i,,n){

         scanf("%lld%lld%lld",&x[i],&y[i],&r[i]);

         q[*i-]=(P){x[i]-r[i],,i}; q[*i]=(P){x[i]+r[i],-,i};

     }

     sort(q+,q+*n+,cmp);

     rep(i,,*n){

         if (q[i].f==-) S.erase((D){q[i].id,}),S.erase((D){q[i].id,-});

         else{

             tmp=q[i].x; set<D>::iterator it=S.lower_bound((D){q[i].id,});

             if (it!=S.end()) f[q[i].id]=((it->k==)?-:)*f[it->id];

             else f[q[i].id]=;

             S.insert((D){q[i].id,}); S.insert((D){q[i].id,-});

         }

     }

     rep(i,,n) ans+=f[i]*r[i]*r[i];

     printf("%lld\n",ans);

     return ;

 }