半平面交的

然而这个代码真的是非常的迷……并不怎么看得懂……

//minamoto#include
    
     #define fp(i,a,b) for(register int i=a,I=b+1;i
     
      I;--i)using namespace std;const int N=1e5+5;const double eps=1e-9;inline int dcmp(const double &a){return fabs(a)>=eps?a<0?-1:1:0;}struct node{double x,y;}pt[N];int tot;inline node operator -(node a,node b){return {a.x-b.x,a.y-b.y};}inline double operator *(node a,node b){return a.x*b.y-a.y*b.x;}struct line{node a,b;}p[N],dq[N];int tp,bt,n;inline bool aboveX(line a){    if(!dcmp(a.b.y-a.a.y))return dcmp(a.b.x-a.a.x)>0;    return dcmp(a.b.y-a.a.y)>0;}inline bool cmp(line a,line b){    if(aboveX(a)!=aboveX(b))return aboveX(a);    if(!dcmp((a.b-a.a)*(b.b-b.a)))return dcmp((a.b-a.a)*(b.b-a.a))<0;    return dcmp((a.b-a.a)*(b.b-b.a))>0;}inline node get(line a,line b){    double a1=a.b.y-a.a.y,b1=a.a.x-a.b.x,c1=a.a*a.b;    double a2=b.b.y-b.a.y,b2=b.a.x-b.b.x,c2=b.a*b.b;    double d=a1*b2-a2*b1;    return {(b2*c1-b1*c2)/d,(a1*c2-a2*c1)/d};}inline bool pd(line a,line b,line c){    node p=get(a,b);    return dcmp((p-c.a)*(c.b-c.a))>-1;}void solve(){    tot=1;    fp(i,1,n)if(dcmp((p[i].b-p[i].a)*(p[tot].b-p[tot].a)))p[++tot]=p[i];    n=tot,dq[bt=1]=p[1],dq[tp=2]=p[2];    fp(i,3,n){        while(tp>bt&&pd(dq[tp],dq[tp-1],p[i]))--tp;        while(tp>bt&&pd(dq[bt],dq[bt+1],p[i]))++bt;        dq[++tp]=p[i];    }    while(tp>bt&&pd(dq[tp],dq[tp-1],dq[bt]))--tp;    while(tp>bt&&pd(dq[bt],dq[bt+1],dq[tp]))++bt;    dq[++tp]=dq[bt],tot=0;    fp(i,bt,tp-1)pt[++tot]=get(dq[i],dq[i+1]);}double area(double s=0){    if(tot<3)return 0;pt[++tot]=pt[1];    fp(i,1,tot-1)s+=pt[i]*pt[i+1];    return 0.5*fabs(s);}int main(){//  freopen("testdata.in","r",stdin);    int T;scanf("%d",&T);    while(T--){        int ps;scanf("%d",&ps);        fp(i,1,ps)scanf("%lf%lf",&pt[i].x,&pt[i].y);        pt[0]=pt[ps];        fp(i,0,ps-1)p[++n].a=pt[i],p[n].b=pt[i+1];    }    sort(p+1,p+1+n,cmp);    solve();double ans=area();printf("%.3lf\n",ans);return 0;}