Bzoj4561 [JLoi2016]圆的异或并-白红宇

Bzoj4561 [JLoi2016]圆的异或并

阅读量：6440 次

发布时间：2019-06-23

本文共 2105 字，大约阅读时间需要 7 分钟。

Time Limit: 30 Sec Memory Limit: 256 MB

Submit: 521 Solved: 224

Description

在平面直角坐标系中给定N个圆。已知这些圆两两没有交点，即两圆的关系只存在相离和包含。求这些圆的异或面

积并。异或面积并为：当一片区域在奇数个圆内则计算其面积，当一片区域在偶数个圆内则不考虑。

Input

第一行包含一个正整数N，代表圆的个数。接下来N行，每行3个非负整数x,y,r，表示一个圆心在(x,y)，半径为r的

圆。保证|x|,|y|,≤10^8，r>0,N<=200000

Output

仅一行一个整数，表示所有圆的异或面积并除以圆周率Pi的结果。

Sample Input

0 0 1

0 0 2

Sample Output

HINT

Source

几何思路题

圆之间没有交点是一个很好的性质，这保证如果圆A被圆B包含，我们从某个方向扫描的时候一定先扫到圆B。

用set维护一个“括号序列”，对于当前的扫描线x，圆与x靠下的交点记为左括号，靠上的交点记为右括号，查询当前圆在几层括号里，若在奇数层就减去这个圆的面积，否则加上

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #define LL long long 8 using namespace std; 9 const int mxn=200010;10 int read(){11 int x=0,f=1;char ch=getchar();12 while(ch<'0' || ch>'9'){ if(ch=='-')f=-1;ch=getchar();}13 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}14 return x*f;15 }16 struct cir{17 int x,y,r;18 }c[mxn];19 struct node{20 int id;21 int x,mk;22 }p[mxn<<1];23 int tmp,cnt=0;24 bool operator < (const node &a,const node &b) {25 double res1=c[a.id].y+a.mk*sqrt((LL)c[a.id].r*c[a.id].r-((LL)tmp-c[a.id].x)*(tmp-c[a.id].x));26 double res2=c[b.id].y+b.mk*sqrt((LL)c[b.id].r*c[b.id].r-((LL)tmp-c[b.id].x)*(tmp-c[b.id].x));27 return (res1==res2 && a.mk
           
            st;33 int n,f[mxn];34 LL ans=0;35 int main(){36 int i,j;37 n=read();38 for(i=1;i<=n;i++){39 c[i].x=read();c[i].y=read();c[i].r=read();40 p[++cnt]=(node){i,c[i].x-c[i].r,1};41 p[++cnt]=(node){i,c[i].x+c[i].r,-1};42 }43 sort(p+1,p+cnt+1,cmp);44 for(i=1;i<=cnt;i++){45 tmp=p[i].x;46 if(p[i].mk==1){47 set
            
             ::iterator it;48 it=st.upper_bound((node){p[i].id,0,-1});49 if(it==st.end())f[p[i].id]=1;50 else{51 if( (*it).mk==1 ) f[p[i].id]=-f[(*it).id];52 else f[p[i].id]=f[(*it).id];53 }54 st.insert((node){p[i].id,0,1});55 st.insert((node){p[i].id,0,-1});56 }57 else{58 st.erase((node){p[i].id,0,1});59 st.erase((node){p[i].id,0,-1});60 }61 }62 for(i=1;i<=n;i++){63 ans+=f[i]*(LL)c[i].r*c[i].r;64 }65 printf("%lld\n",ans);66 return 0;67 }