题目大意：给定n个凸多边形，求交集的面积
时隔多年我终于把完整的半平面交搞出来了……真尼玛艰辛……
曾经写了一发 RE到死 于是就搁置0.0 今天写一发又是WA到死的节奏……
不多说直接上代码 其实刘汝佳同学写麻烦了 每次插入一个半平面之后不用两端都删的 只删一端 最后再处理两端的部分就行
300题留念……切了道模板题也不错
#include <cmath>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 510#define EPS 1e-7using namespace std;struct point{double x,y;point(){}point(double _,double __):x(_),y(__){}point operator + (const point &p) const{return point(x+p.x,y+p.y);}point operator – (const point &p) const{return point(x-p.x,y-p.y);}double operator * (const point &p) const{return x*p.y-y*p.x;}point operator * (const double &rate) const{return point(x*rate,y*rate);}void Read(){scanf("%lf%lf",&x,&y);}}points[M];struct line{point p,v;double alpha;line(){}line(const point &p1,const point &p2):p(p1),v(p2-p1){alpha=atan2(v.y,v.x);}bool operator < (const line &l) const{return alpha < l.alpha;}}lines[M];int n,m,tot;line *q[M];int r,h;double ans;bool Onleft(const point &p,const line &l){return (l.p-p)*l.v>=0;}point Get_Intersection(const line &l1,const line &l2){point u=l1.p-l2.p;double temp=(l2.v*u)/(l1.v*l2.v);return l1.p+l1.v*temp;}void Get_Half_Plane_Intersection(){int i;for(i=1;i<=tot;i++){while( r-h>=2 && !Onleft(Get_Intersection(*q[r],*q[r-1]),lines[i]) )q[r–]=0x0;if( r-h>=1 && fabs(lines[i].v*q[r]->v)<=0 )q[r]=Onleft(lines[i].p,*q[r])?&lines[i]:q[r];else q[++r]=&lines[i];}while( r-h>=2 && !Onleft(Get_Intersection(*q[h+1],*q[h+2]),*q[r]) )q[++h]=0x0;while( r-h>=2 && !Onleft(Get_Intersection(*q[r],*q[r-1]),*q[h+1]) )q[r–]=0x0;}int main(){int i,j;cin>>n;for(i=1;i<=n;i++){point first,p1,p2;scanf("%d",&m);first.Read();p2=first;for(j=2;j<=m;j++){p1=p2;p2.Read();lines[++tot]=line(p1,p2);}lines[++tot]=line(p2,first);}sort(lines+1,lines+tot+1);Get_Half_Plane_Intersection();if(r-h<=2)return puts("0.000"),0;tot=0;for(i=h+2;i<=r;i++)points[++tot]=Get_Intersection(*q[i],*q[i-1]);points[++tot]=Get_Intersection(*q[r],*q[h+1]);for(i=2;i<=tot;i++)ans+=points[i-1]*points[i];ans+=points[tot]*points[1];printf("%.3lf\n",ans/2);return 0;}
，谦受益，满招损。
