[文章目录]
Description
逆时针给出n个凸多边形的顶点坐标，求它们交的面积。2<=n<=10，3<=点数<=50
半平面交，求出凸包面积即可。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define eps 1e-9
using namespace std;
int n,np,q[600];
struct point
{
double x,y;
point(){}
point(double _x,double _y){x=_x,y=_y;}
point operator + (const point &z)const {return point(x+z.x,y+z.y);}
point operator - (const point &z)const {return point(x-z.x,y-z.y);}
double operator *(const point &z)const {return x*z.y-y*z.x;}
point operator *(const double &z)const {return point(x*z,y*z);}
}d[600];
struct line
{
point p,v;
double a;
line(){};
line(point x,point y){p=x,v=y,a=atan2(v.y,v.x);}
}l[600];
point getpo(line l1,line l2)
{
point u=l1.p-l2.p;
double t=(l2.v*u)/(l1.v*l2.v);
return l1.p+l1.v*t;
}
bool onlft(line x,point y)
{
return x.v*(y-x.p)>eps;
}
bool cmp(line x,line y)
{
if(fabs(x.a-y.a)<eps) return onlft(x,y.p);
return x.a<y.a;
}
void half_plane()
{
sort(l+1,l+n+1,cmp);
int t=1;
for(int i=2;i<=n;++i) if(fabs(l[i].a-l[t].a)>eps) l[++t]=l[i];
n=t; int h=1; q[1]=t=1;
for(int i=2;i<=n;++i)
{
while(h<t&&onlft(l[i],getpo(l[q[t]],l[q[t-1]]))) --t;
while(h<t&&onlft(l[i],getpo(l[q[h]],l[q[h+1]]))) ++h;
q[++t]=i;
}
while(h<t&&onlft(l[q[h]],getpo(l[q[t]],l[q[t-1]]))) --t;
while(h<t&&onlft(l[q[t]],getpo(l[q[h]],l[q[h+1]]))) ++h;
q[++t]=q[h];
for(int i=h;i<t;++i) d[++np]=getpo(l[q[i]],l[q[i+1]]);
}
double getarea()
{
if(np<3) return 0;
double re=0;
for(int i=1;i<np;++i) re+=d[i]*d[i+1];
re+=d[np]*d[1];
return fabs(re/2);
}
int main()
{
scanf("%d",&n);
int m,t=0;
for(int i=1;i<=n;++i)
{
scanf("%d",&m);
for(int j=1;j<=m;++j) scanf("%lf%lf",&d[j].x,&d[j].y);
for(int j=1;j<=m;++j) l[++t]=line(d[j],d[j]-d[j%m+1]);
}
n=t;
half_plane();
printf("%.3lf",getarea());
return 0;
}