计数方法（扫描线）：JLOI 2016 圆的异或并

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

Sample Output

　　这道题是模板题，经典题。

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <cmath>

 #include <set>

 #include <cassert>

 using namespace std;

 const int N=,M=;

 int n,px[N],py[N],r[N],top,T;

 long long sqr(long long a){return a*a;}

 struct Point{

     int id,x,tp;

     friend bool operator<(Point x,Point y){

         double a=py[x.id]+x.tp*sqrt(sqr(r[x.id])-sqr(T-px[x.id]));

         double b=py[y.id]+y.tp*sqrt(sqr(r[y.id])-sqr(T-px[y.id]));

         if(a!=b)return a<b;assert(x.id==y.id);return x.tp<y.tp;

     }

 }st[M];

 bool cmp(Point a,Point b){

     return a.x<b.x;

 }

 int res[N];

 set<Point>s;

 set<Point>::iterator it;

 long long ans;

 int main(){

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

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

     scanf("%d",&n);

     for(int i=;i<=n;i++){

         scanf("%d%d%d",&px[i],&py[i],&r[i]);

         st[++top]=(Point){i,px[i]-r[i],};

         st[++top]=(Point){i,px[i]+r[i],-};

     }

     sort(st+,st+top+,cmp);

     for(int i=;i<=top;i++){

         Point x=st[i];T=x.x;

         if(x.tp==){

             it=s.upper_bound((Point){x.id,,});

             if(it==s.end())res[x.id]=;

             else{

                 Point y=*it;

                 if(y.tp==)res[x.id]=-res[y.id];

                 else res[x.id]=res[y.id];

             }

             s.insert((Point){x.id,,-});

             s.insert((Point){x.id,,});

         }

         else{

             s.erase((Point){x.id,,-});

             s.erase((Point){x.id,,});

         }

     }

     for(int i=;i<=n;i++)

         ans+=res[i]*sqr(r[i]);

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

     return ;

 }

秒客网