半平面交

ez_lcw · 2019-10-31 16:51:06 · 个人记录

半平面交

#include<bits/stdc++.h>

#define eps 1e-6
#define N 510

using namespace std;

struct Point
{
    double x,y;
    Point(){};
    Point(double a,double b)
    {
        x=a,y=b;
    }
}p[N],e[N];

struct Line
{
    Point s,t;
    double d;
    Line(){};
    Line(Point a,Point b)
    {
        s=a,t=b;
    }
}l[N],q[N];

Point operator + (Point a,Point b)
{
    return Point{a.x+b.x,a.y+b.y};
}

Point operator - (Point a,Point b)
{
    return Point{a.x-b.x,a.y-b.y};
}

Point operator * (Point a,double x)
{
    return Point{a.x*x,a.y*x};
}

int n,cnt,cnt1;
double ans;

double cross(Point a,Point b)
{
    return a.x*b.y-b.x*a.y;
}

double dis(Point a,Point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int compare(double x,double y)
{
    if(fabs(x-y)<eps)return 0;
    return x-y<0?-1:1;
}

bool cmp(Line a,Line b)
{
    if(!compare(a.d,b.d))return cross(a.t-a.s,b.t-a.s)>0;
    return a.d<b.d;
}

bool onright(Point a,Line l)
{
    return compare(cross(l.t-l.s,a-l.s),0)>0?0:1;
}

Point intersection(Line a,Line b)
{
    Point u=a.s-b.s;
    Point v=a.t-a.s;
    Point w=b.t-b.s;
    double t=cross(w,u)/cross(v,w);
    return a.s+v*t;
}

double angle(Point a)
{
    return atan2(a.y,a.x);
}

void half()
{
    sort(l+1,l+cnt+1,cmp);
    cnt1=0;
    for(int i=1;i<cnt;i++)
    {
        if(!compare(l[i+1].d-l[i].d,0))continue;
        l[++cnt1]=l[i];
    }
    l[++cnt1]=l[cnt];
    cnt=cnt1;
    int L=1,R=0;
    q[++R]=l[1],q[++R]=l[2];
    for(int i=3;i<=cnt;i++)
    {
        while(L<R&&onright(intersection(q[R],q[R-1]),l[i]))R--;
        while(L<R&&onright(intersection(q[L],q[L+1]),l[i]))L++;
        q[++R]=l[i];
    }
    while(L<R&&onright(intersection(q[R],q[R-1]),q[L]))R--;
    while(L<R&&onright(intersection(q[L],q[L+1]),q[R]))L++;
    q[++R]=q[L];
    cnt1=0;
    for(int i=L;i<R;i++)e[++cnt1]=intersection(q[i],q[i+1]);
    e[++cnt1]=e[1];
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int m;
        scanf("%d",&m);
        Point last,st;
        for(int j=1;j<=m;j++)
        {
            double x,y;
            scanf("%lf%lf",&x,&y);
            if(j==1)
            {
                last=st=Point{x,y};
                continue;
            }
            l[++cnt]=Line{last,Point{x,y}};
            last=Point{x,y};
        }
        l[++cnt]=Line{last,st};
    }
    for(int i=1;i<=cnt;i++)l[i].d=angle(l[i].s-l[i].t);
    half();
    if(cnt1<3)
    {
        puts("0.000");
        return 0;
    }
    for(int i=1;i<cnt1;i++)ans+=cross(e[i],e[i+1]);
    printf("%.3lf\n",ans/2.0);
    return 0;
}