【BZOJ 2618】 2618: [Cqoi2006]凸多边形 （半平面交）

  1 #include<cstdio>  2 #include<cstdlib>  3 #include<cstring>  4 #include<iostream>  5 #include<algorithm>  6 #include<cmath>  7 using namespace std;  8 #define Maxn 1100  9  10 struct P {double x,y;}; 11 struct L {P a,b;double slop;}l[Maxn]; 12 //半平面只方向向量a->b的左部分 13 //slop 极角 14 int cnt; 15  16 P operator - (P x,P y) 17 { 18     P tt; 19     tt.x=x.x-y.x; 20     tt.y=x.y-y.y; 21     return tt; 22 } 23  24 P operator + (P x,P y) 25 { 26     P tt; 27     tt.x=x.x+y.x; 28     tt.y=x.y+y.y; 29     return tt; 30 } 31  32 double Dot(P x,P y) {return x.x*y.x+x.y*y.y;} 33 double Cross(P x,P y) {return x.x*y.y-x.y*y.x;} 34 // bool operator < (L x,L y) {return x.slop<y.slop;} 35  36 bool operator < (L a,L b) 37 { 38     if(a.slop!=b.slop)return a.slop<b.slop; 39     return Cross(a.b-a.a,b.b-a.a)>0; 40 } 41  42 P operator * (P X,double y) 43 { 44     P tt; 45     tt.x=X.x*y; 46     tt.y=X.y*y; 47     return tt; 48 } 49  50 P a[Maxn]; 51 L q[Maxn]; 52 int tot; 53  54 P inter(L a,L b) 55 { 56     P X=a.a-a.b,Y=b.a-b.b,nw; 57     double tt; 58     nw=b.a-a.a; 59     tt=Cross(nw,X)/Cross(X,Y); 60     P ans=b.a+Y*tt; 61     return ans; 62 } 63  64 bool jud(L a,L b,L c) 65 { 66     P p=inter(a,b); 67     return Cross(c.b-c.a,p-c.a)<0; 68 } 69  70 void opp() 71 { 72     for(int i=1;i<=cnt;i++) 73     { 74         printf("%.2lf %.2lf %.2lf %.2lf = %.2lf \n",l[i].a.x,l[i].a.y,l[i].b.x,l[i].b.y,l[i].slop); 75     } 76     printf("\n"); 77 } 78  79 void output() 80 { 81     for(int i=1;i<=tot;i++) printf("%2lf %.2lf\n",a[i].x,a[i].y); 82     printf("\n"); 83 } 84  85 void op(int L,int R) 86 { 87     for(int i=L;i<=R;i++) 88         printf("%lf %lf %lf %lf\n",l[i].a.x,l[i].a.y,l[i].b.x,l[i].b.y); 89     printf("\n"); 90 } 91  92 void ffind() 93 { 94     for(int i=1;i<=cnt;i++) 95       l[i].slop=atan2(l[i].b.y-l[i].a.y,l[i].b.x-l[i].a.x); 96     sort(l+1,l+1+cnt); 97      98     // opp(); 99     100     int L=1,R=0;101     //去重？102     tot=0;103     for(int i=1;i<=cnt;i++)104     {105         if(l[i].slop!=l[i-1].slop) tot++;106         l[tot]=l[i];107     }108     cnt=tot;tot=0;109     // opp();110     q[++R]=l[1];q[++R]=l[2];111     for(int i=3;i<=cnt;i++)112     {113         while(L<R&&jud(q[R-1],q[R],l[i])) R--;114         while(L<R&&jud(q[L+1],q[L],l[i])) L++;115         q[++R]=l[i];116         // op(L,R);117     }118     while(L<R&&jud(q[R-1],q[R],q[L])) R--;119     while(L<R&&jud(q[L+1],q[L],q[R])) L++;120     q[R+1]=q[L];121     for(int i=L;i<=R;i++)122       a[++tot]=inter(q[i],q[i+1]);123   // output();124   125   // output();126 }127 128 void init()129 {130     int n;131     /*scanf("%d",&n);132     for(int i=1;i<=n;i++)133     {134         scanf("%lf%lf%lf%lf\n",&l[i].a.x,&l[i].a.y,&l[i].b.x,&l[i].b.y);135     }136     cnt=n;*/137     scanf("%d",&n);138     cnt=0;139     for(int i=1;i<=n;i++)140     {141         int m;142         scanf("%d",&m);143         P ft,now;144         scanf("%lf%lf",&ft.x,&ft.y);145         now=ft;146         for(int j=2;j<=m;j++)147         {148             P nw;149             scanf("%lf%lf",&nw.x,&nw.y);150             l[++cnt].b=nw;151             l[cnt].a=now;152             now=nw;153         }154         l[++cnt].a=now;l[cnt].b=ft;155     // opp();156     }157     158     159     for(int i=1;i<=cnt;i++)160       l[i].slop=atan2(l[i].b.y-l[i].a.y,l[i].b.x-l[i].a.x);161     // opp();162     163 }164 165 void get_area()166 {167     double ans=0;168     for(int i=1;i<tot;i++)169     {170         ans+=Cross(a[i],a[i+1]);171     }172     ans+=Cross(a[tot],a[1]);173     if(tot<3) ans=0;174     printf("%.3lf\n",ans/2);175 }176 177 int main()178 {179     init();180     ffind();181     // output();182     get_area();183     return 0;184 }