Description

則相交部分的面積為5.233。

Input

第一行有一個(gè)整數(shù)n，表示凸多邊形的個(gè)數(shù)，以下依次描述各個(gè)多邊形。第i個(gè)多邊形的第一行包含一個(gè)整數(shù)m_i，表示多邊形的邊數(shù)，以下m_i行每行兩個(gè)整數(shù)，逆時(shí)針給出各個(gè)頂點(diǎn)的坐標(biāo)。

Output

    輸出文件僅包含一個(gè)實(shí)數(shù)，表示相交部分的面積，保留三位小數(shù)。

Sample Input

Sample Output

HINT

100%的數(shù)據(jù)滿足：2<=n<=10，3<=m_i<=50，每維坐標(biāo)為[-1000,1000]內(nèi)的整數(shù)

Source

題解：半平面交

#include<iostream>  #include<cstdio>  #include<algorithm>  #include<cstring>  #include<cmath>  #define  N 2000  #define eps 1e-8  #define inf 1e9  using namespace std;  struct vector {      double x,y;      vector (double X=0,double Y=0){          x=X,y=Y;      }  }a[N],p[N],tmp[N];  typedef vector point;  vector Operator -(vector a,vector b){      return vector (a.x-b.x,a.y-b.y);  }  vector operator +(vector a,vector b){      return vector (a.x+b.x,a.y+b.y);  }  vector operator *(vector a,double t){      return vector (a.x*t,a.y*t);  }  int n,m; int dcmp(double x){	if (fabs(x)<eps) return 0;	return x<0?-1:1;} double cross(vector a,vector b)  {      return a.x*b.y-a.y*b.x;  }  point glt(point a,point a1,point b,point b1)  {      vector v=a1-a; vector w=b1-b;      vector u=a-b;      double t=cross(w,u)/cross(v,w);      return a+v*t;  }  void init()  {     m=0;     p[m++]=point(inf,inf);     p[m++]=point(-inf,inf);     p[m++]=point(-inf,-inf);     p[m++]=point(inf,-inf);  }  void cut(point a,point b)  {      int cnt=0;      memset(tmp,0,sizeof(tmp));      for (int i=0;i<m;i++){          double c=cross(b-a,p[i]-a);          double d=cross(b-a,p[(i+1)%m]-a);          if (dcmp(c)<=0) tmp[cnt++]=p[i];          if (dcmp(c)*dcmp(d)<0)            tmp[cnt++]=glt(a,b,p[i],p[(i+1)%m]);      }      m=cnt;      for (int i=0;i<cnt;i++) p[i]=tmp[i];  }  int main()  {      freopen("a.in","r",stdin);      int T;      scanf("%d",&T);      init();    for (int t=1;t<=T;t++) {	    scanf("%d",&n);	    for (int j=1;j<=n;j++) scanf("%lf%lf",&a[j].x,&a[j].y);	    a[n+1]=a[1];        for (int i=2;i<=n+1;i++)            cut(a[i],a[i-1]);  	}    double area=0;      p[m]=p[0];      for (int i=1;i<m;i++)        area+=cross(p[i]-p[0],p[i+1]-p[0]);      PRintf("%.3lf/n",fabs(area)/2);   }