bzoj 2618: [Cqoi2006]凸多边形 （半平面交）

Description

则相交部分的面积为5.233。

Input

第一行有一个整数n，表示凸多边形的个数，以下依次描述各个多边形。第i个多边形的第一行包含一个整数m_i，表示多边形的边数，以下m_i行每行两个整数，逆时针给出各个顶点的坐标。

Output

    输出文件仅包含一个实数，表示相交部分的面积，保留三位小数。

Sample Input

Sample Output

HINT

100%的数据满足：2<=n<=10，3<=m_i<=50，每维坐标为[-1000,1000]内的整数

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);   }