G54 半平面交 双端队列【计算几何】

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-12;
const int N=510;

struct Point{double x,y;}P[N];
Point operator+(Point a,Point b) {return {a.x+b.x,a.y+b.y};}
Point operator-(Point a,Point b) {return {a.x-b.x,a.y-b.y};}
Point operator*(Point a,double t) {return {a.x*t,a.y*t};}
Point operator/(Point a,double t) {return {a.x/t,a.y/t};}

struct Line {Point s,e;}L[N],q[N];int cnt;

double det(Point a,Point b) {return a.x*b.y-a.y*b.x;}
double angle(Line L0) {return atan2(L0.e.y-L0.s.y, L0.e.x-L0.s.x);}
bool cmp(Line L1, Line L2)
{
    double A=angle(L1), B=angle(L2);
    return fabs(A-B)>eps ? A<B : det(L1.e-L1.s, L2.e-L1.s)<0;//如果平行，L1在L2的左边 
}
Point crosspoint(Line L1,Line L2)
{
    Point a=L1.s,b=L1.e,c=L2.s,d=L2.e;
    double s1=det(c-a,b-a);
    double s2=det(d-a,b-a);
    return (c*s2-d*s1)/(s2-s1);
}
bool right(Line L0,Line L1,Line L2)
{
    Point p1=L0.e-L0.s,p2=crosspoint(L1,L2)-L0.s;
    return det(p1,p2)<0;
}
double half_plane()
{
    sort(L+1,L+cnt+1,cmp);
    int h=1,t=1;q[1]=L[1];
    for(int i=2; i<=cnt; i++)
    {
        if(angle(L[i])-angle(L[i-1])<eps) continue;
        while(h<t && right(L[i],q[t],q[t-1]))t--;
        while(h<t && right(L[i],q[h],q[h+1]))h++;
        q[++t]=L[i];
    }
    while(h<t && right(q[h],q[t],q[t-1]))t--;

    q[++t]=q[h]; //封口
    
    double res=0;int k=0;
    for(int i=h; i<t; i++)P[++k]=crosspoint(q[i],q[i+1]);
    for(int i=2; i<k; i++)res+=det(P[i]-P[1],P[i+1]-P[1]);
    return res/2; //面积
}

int main()
{
    int n;scanf("%d",&n);
    cnt=0;
    while(n--)
    {
        int m;scanf("%d",&m);
        for(int i=1; i<=m; i++)scanf("%lf%lf",&P[i].x,&P[i].y);
        for(int i=1; i<=m; i++)L[++cnt]={P[i],P[i%m+1]};
    }
    printf("%.3lf\n", half_plane());
    return 0;
}