思路:考试的时候我非常地**，写了圆并，然后还TM写了半平面交和三角剖分，虽然只有30分。。但是看在我写了500行的份上还是挂着吧。。

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 const double Pi=acos(-1);  7 const double eps=1e-10;  8 int n,m,cnt,tot,num;  9 bool pd[200005],check; 10 int read(){ 11     int t=0,f=1;char ch=getchar(); 12     while (ch<'0'||ch>'9') {
   if (ch=='-') f=-1;ch=getchar();} 13     while ('0'<=ch&&ch<='9') {t=t*10+ch-'0';ch=getchar();} 14     return t*f; 15 } 16 struct node{ 17     double l,r; 18 }L[200005]; 19 struct Point{ 20     double x,y; 21     Point(){} 22     Point(double x0,double y0):x(x0),y(y0){} 23 }p[200005],c[200005],d[200005]; 24 struct Line{ 25     Point s,e; 26     double slop; 27     Line(){} 28     Line(Point s0,Point e0):s(s0),e(e0){} 29 }l[200005],q[200005]; 30 struct Circle{ 31     Point p; 32     double r; 33     Circle(){} 34     Circle(double x0,double y0,double r0):p(Point(x0,y0)),r(r0){}     35 }a[200005]; 36 bool cmp2(node a,node b){ 37     if (fabs(a.l-b.l)
          
           eps) return 1;if (x<-eps) return -1;return 0;} 41 double operator *(Point p1,Point p2){ return p1.x*p2.y-p1.y*p2.x;} 42 double operator /(Point p1,Point p2){ return p1.x*p2.x+p1.y*p2.y;} 43 Point operator -(Point p1,Point p2){ return Point(p1.x-p2.x,p1.y-p2.y);} 44 Point operator +(Point p1,Point p2){ return Point(p1.x+p2.x,p1.y+p2.y);} 45 Point operator *(Point p1,double x){ return Point(p1.x*x,p1.y*x);} 46 Point operator /(Point p1,double x){ return Point(p1.x/x,p1.y/x);} 47 double sqr(double x){ return x*x;} 48 double llen(Point p1){ return sqrt(sqr(p1.x)+sqr(p1.y)); } 49 double dis(Point p1,Point p2){ return llen(p1-p2);} 50 double dis(Point p1){ return llen(p1);} 51 Point evector(Point p1){ double t=llen(p1);if (t
           
            0; 55 } 56 bool cmp(Point p1,Point p2){ 57 double t=(p1-p[1])*(p2-p[1]); 58 if (fabs(t)
            
             0; 60 } 61 bool conclude(Circle p1,Circle p2){ 62 double Len=dis(p1.p,p2.p); 63 if (fabs(p1.r-p2.r)>=Len) return 1; 64 return 0; 65 } 66 bool intersect(Circle p1,Circle p2){ 67 double Len=dis(p1.p,p2.p); 68 if (fabs(p1.r-p2.r)<=Len&&Len<=p1.r+p2.r) return 1; 69 return 0; 70 } 71 double dist_line(Line p){ 72 double A,B,C,dist; 73 A=p.s.y-p.e.y; 74 B=p.s.x-p.e.x; 75 C=p.s.x*p.e.y-p.s.y*p.e.x; 76 dist=fabs(C)/sqrt(sqr(A)+sqr(B)); 77 return dist; 78 } 79 double dist_line(Point p1,Line p){ 80 p.s.x-=p1.x; 81 p.e.x-=p1.x; 82 p.s.y-=p1.y; 83 p.e.y-=p1.y; 84 return dist_line(p); 85 } 86 double get_cos(double a,double b,double c){ 87 return (b*b+c*c-a*a)/(2*b*c); 88 } 89 double get_angle(Point p1,Point p2){ 90 if (!sgn(dis(p1))||!sgn(dis(p2))) return 0.0; 91 double A,B,C; 92 A=dis(p1); 93 B=dis(p2); 94 C=dis(p1,p2); 95 if (C<=eps) return 0.0; 96 return fabs(acos(get_cos(C,A,B))); 97 } 98 Point get_point(Point p){ 99 double T=sqr(p.x)+sqr(p.y);100 return Point(sgn(p.x)*sqrt(sqr(p.x)/T),sgn(p.y)*sqrt(sqr(p.y)/T));101 }102 bool bigconclude(Circle p1,Circle p2,Point p){103 Point e1=p2.p-p1.p;104 Point e2=p-p1.p;105 if (sgn(e1/e2)<0) return 1;106 else return 0;107 }108 double S(Point p1,Point p2,Point p3){109 return fabs((p2-p1)*(p3-p1))/2;110 }111 double work(Point p1,Point p2,double R){112 Point O=Point(0,0);113 double f=sgn(p1*p2),res=0;114 if (!sgn(f)||!sgn(dis(p1))||!sgn(dis(p2))) return 0.0;115 double l=dist_line(Line(p1,p2));116 double a=dis(p1);117 double b=dis(p2);118 double c=dis(p1,p2);119 if (a<=R&&b<=R){120 return fabs(p1*p2)/2.0*f;121 }122 if (a>=R&&b>=R&&l>=R){123 double ang=get_angle(p1,p2);124 return fabs((ang/(2.0))*(R*R))*f;125 }126 if (a>=R&&b>=R&&l<=R&&(get_cos(a,b,c)<=0||get_cos(b,a,c)<=0)){127 double ang=get_angle(p1,p2);128 return fabs((ang/(2.0))*(R*R))*f;129 }130 if (a>=R&&b>=R&&l<=R&&(get_cos(a,b,c)>0&&get_cos(b,a,c)>0)){131 double dist=dist_line(Line(p1,p2));132 double len=sqrt(sqr(R)-sqr(dist))*2.0;133 double ang1=get_angle(p1,p2);134 double cos2=get_cos(len,R,R);135 res+=fabs(len*dist/2.0);136 double ang2=ang1-acos(cos2);137 res+=fabs((ang2/(2))*(R*R));138 return res*f;139 }140 if ((a>=R&&b
             
              
               =R)){141 if (b>a) std::swap(a,b),std::swap(p1,p2);142 double T=sqr(p1.x-p2.x)+sqr(p1.y-p2.y);143 Point u=Point(sgn(p1.x-p2.x)*sqrt(sqr(p1.x-p2.x)/T),sgn(p1.y-p2.y)*sqrt(sqr(p1.y-p2.y)/T));144 double dist=dist_line(Line(p1,p2));145 double len=sqrt(R*R-dist*dist);146 double len2=sqrt(sqr(dis(p2))-sqr(dist));147 if (fabs(dis(p2+u*len2)-dist)<=eps) len+=len2;148 else len-=len2;149 Point p=p2+u*len;150 res+=S(O,p2,p);151 double ang=get_angle(p1,p);152 res+=fabs((ang/2.0)*R*R);153 return res*f;154 }155 return 0;156 }157 Point inter(Line p1,Line p2){158 double t1=(p2.e-p1.s)*(p1.e-p1.s);159 double t2=(p1.e-p1.s)*(p2.s-p1.s);160 if (fabs(t1+t2)
               
                =R&&b>=R&&l>=R){265 double ang=get_angle(p1,p2);266 res=abs((ang/(2.0))*(R*R));267 }268 else269 if (a>=R&&b>=R&&l<=R&&(get_cos(a,b,c)<=0||get_cos(b,a,c)<=0)){270 double ang=get_angle(p1,p2);271 res=fabs((ang/(2.0))*(R*R));272 }273 else274 if (a>=R&&b>=R&&l<=R&&(get_cos(a,b,c)>0&&get_cos(b,a,c)>0)){275 double dist=dist_line(Line(p1,p2));276 double len=sqrt(sqr(R)-sqr(dist))*2.0;277 double ang1=get_angle(p1,p2);278 double cos2=get_cos(len,R,R);279 res+=fabs(len*dist/2.0);280 double ang2=ang1-acos(cos2);281 res+=fabs((ang2/(2))*(R*R));282 }283 else284 if ((a>=R&&b
                
                 
                  =R)){285 if (b>a) std::swap(a,b),std::swap(p1,p2);286 double T=sqr(p1.x-p2.x)+sqr(p1.y-p2.y);287 Point u=Point(sgn(p1.x-p2.x)*sqrt(sqr(p1.x-p2.x)/T),sgn(p1.y-p2.y)*sqrt(sqr(p1.y-p2.y)/T));288 double dist=dist_line(Line(p1,p2));289 double len=sqrt(R*R-dist*dist);290 double len2=sqrt(sqr(dis(p2))-sqr(dist));291 if (fabs(dis(p2+u*len2)-dist)<=eps) len+=len2;292 else len-=len2;293 Point p=p2+u*len;294 res+=S(O,p2,p);295 double ang=get_angle(p1,p);296 res+=fabs((ang/2.0)*R*R);297 }298 int in1=((sgn(c1*p1)*sgn(p1*c2))>=0);299 int in2=((sgn(c1*p2)*sgn(p2*c2))>=0);300 if (in1&&in2) return res*rev;301 if (!in1){302 if (dis(p1)<=R){303 Point sb=inter(Line(O,c1),Line(p1,p2));304 double Di=dis(sb);305 if (Di<=R) res-=S(O,sb,p1);306 else{307 Point sx=inter(Circle(0,0,R),Line(p1,p2),p1); 308 double ang=get_angle(c1,sx);309 res-=fabs((ang/2.0)*R*R);310 res-=S(O,sx,p1);311 }312 }else{313 Point sb=inter(Line(O,c1),Line(p1,p2));314 double Di=dis(sb);315 if (Di>=R){316 double ang=get_angle(c1,p1);317 res-=fabs((ang/2.0)*R*R);318 }else{319 Point sx=inter(Circle(0,0,R),Line(p1,p2),p1);320 double ang2=get_angle(p1,sx);321 res-=fabs((ang2/2.0)*R*R);322 res-=S(sb,sx,O);323 }324 }325 }326 if (!in2){327 if (dis(p2)<=R){328 Point sb=inter(Line(O,c2),Line(p1,p2));329 double Di=dis(sb);330 if (Di<=R) res-=S(O,sb,p2);331 else{332 Point sx=inter(Circle(0,0,R),Line(p2,p1),p2); 333 double ang=get_angle(c2,sx);334 res-=fabs((ang/2.0)*R*R);335 res-=S(O,sx,p2);336 }337 }else{338 Point sb=inter(Line(O,c2),Line(p1,p2));339 double Di=dis(sb);340 if (Di>=R){341 double ang=get_angle(c2,p2);342 res-=fabs((ang/2.0)*R*R);343 }else{344 Point sx=inter(Circle(0,0,R),Line(p2,p1),p2);345 double ang2=get_angle(p2,sx);346 res-=fabs((ang2/2.0)*R*R);347 res-=S(sb,sx,O);348 }349 }350 }351 return res*rev;352 }353 double Gworking2(double a1,double a2,Circle w){354 double res=0,r=w.r;355 Point p1=Point(r*cos(a1),r*sin(a1));356 Point p2=Point(r*cos(a2),r*sin(a2));357 p[n+1]=p[1];358 for (int i=1;i<=n+1;i++)359 c[i]=Point(p[i].x-w.p.x,p[i].y-w.p.y);360 for (int i=1;i<=n;i++)361 res+=gworking2(c[i],c[i+1],p1,p2,r); 362 return res;363 }364 void graham(){365 int k=1;366 for (int i=2;i<=n;i++)367 if (p[i].y
                  
                   
                    1&&(c[top]-c[top-1])*(p[i]-c[top])<=0) top--;372 c[++top]=p[i]; 373 }374 n=top;375 for (int i=1;i<=top;i++)376 p[i]=c[i];377 }378 void Work(Circle p1,Point a1,Point a2){379 Point O=p1.p;double r=p1.r;380 a1.x-=O.x;a2.x-=O.x;381 a1.y-=O.y;a2.y-=O.y;382 double x1=atan2(a1.y,a1.x),x2=atan2(a2.y,a2.x);383 if (x1<0) x1+=2*Pi;384 if (x2<0) x2+=2*Pi;385 if (x1<=x2){386 cnt++;387 L[cnt].l=x1;388 L[cnt].r=x2;389 }else{390 cnt++;391 L[cnt].l=x1;392 L[cnt].r=2*Pi;393 cnt++;394 L[cnt].l=0.0;395 L[cnt].r=x2;396 }397 }398 void add(Circle p1,Circle p2){399 double x1=p1.p.x,x2=p2.p.x,y1=p1.p.y,y2=p2.p.y,r1=p1.r,r2=p2.r;400 double A=-2*(x1+x2),B=-2*(y1+y2),C=sqr(x1)+sqr(x2)+sqr(y1)+sqr(y2)-sqr(r1)-sqr(r2);401 Point S,E;402 if (fabs(A)
                    
                     Reach){481 if (j==126) ww++;482 ans+=Gworking1(Last,Reach,a[i]);483 Last=L[j].l;484 ans+=Gworking2(Reach,L[j].l,a[i]);485 Reach=L[j].r;486 }else{487 Reach=L[j].r;488 }489 if (fabs(Reach-2*Pi)
                     
                      =eps){493 ans+=Gworking1(Last,Reach,a[i]);494 ans+=Gworking2(Reach,2*Pi,a[i]);495 }496 }497 printf("%.8lf\n",ans);498 return 0;499 }