BZOJ

题意：求n个凸多边形的交面积。
半平面交模板题。
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 typedef double db;
 5 const int N=1000+10,inf=0x3f3f3f3f;
 6 const db pi=acos(-1),eps=1e-8;
 7 struct P {
 8     db x,y;
 9     P operator-(P b) {return {x-b.x,y-b.y};}
10     P operator+(P b) {return {x+b.x,y+b.y};}
11     P operator*(db b) {return {x*b,y*b};}
12     bool operator<(const P& b)const {return x!=b.x?x<b.x:y<b.y;}
13     bool operator==(const P& b)const {return x==b.x&&y==b.y;}
14 } p[N],hpi[N];
15 db cross(P a,P b) {return a.x*b.y-a.y*b.x;}
16 struct Line {
17     P p,v;
18     db rad()const {return atan2(v.y,v.x);};
19 } line[N],q[N];
20 bool onleft(P p,Line a) {return cross(a.v,p-a.p)>0;}
21 P its(Line a,Line b) {
22     P v=a.p-b.p;
23     db t=cross(b.v,v)/cross(a.v,b.v);
24     return a.p+a.v*t;
25 }
26 bool operator<(const Line& a,const Line& b) {
27     db r1=a.rad(),r2=b.rad();
28     return fabs(r1-r2)>eps?r1<r2:onleft(a.p,b);
29 }
30 int n,m,nl,nhpi;
31 void HPI() {
32     sort(line,line+nl);
33     int hd=0,tl=-1;
34     for(int i=0; i<nl; ++i) {
35         if(hd<=tl&&fabs(line[i].rad()-q[tl].rad())<eps)continue;
36         if(hd<tl&&cross(q[hd].v,q[tl].v)<0&&onleft(its(q[hd],q[tl]),line[i]))continue;
37         for(; hd<tl&&!onleft(its(q[tl-1],q[tl]),line[i]); --tl);
38         for(; hd<tl&&!onleft(its(q[hd],q[hd+1]),line[i]); ++hd);
39         q[++tl]=line[i];
40     }
41     nhpi=0;
42     for(int i=hd; i<tl; ++i)hpi[nhpi++]=its(q[i],q[i+1]);
43     hpi[nhpi++]=its(q[tl],q[hd]);
44 }
45 db area() {
46     db ret=0;
47     for(int i=1; i<nhpi-1; ++i)ret+=cross(hpi[i]-hpi[0],hpi[i+1]-hpi[0]);
48     return fabs(ret/2);
49 }
50 
51 int main() {
52     for(scanf("%d",&m); m--;) {
53         scanf("%d",&n);
54         for(int i=0; i<n; ++i)scanf("%lf%lf",&p[i].x,&p[i].y);
55         for(int i=0; i<n; ++i)line[nl++]= {p[i],p[(i+1)%n]-p[i]};
56     }
57     HPI();
58     printf("%.3f
",area());
59     return 0;
60 }