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

2618: [Cqoi2006]凸多边形

Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 656 Solved: 340
[Submit][Status][Discuss]

Description

逆时针给出n个凸多边形的顶点坐标，求它们交的面积。例如n=2时，两个凸多边形如下图：

则相交部分的面积为5.233。

Input

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

Output

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

Sample Input

2
6
-2 0
-1 -2
1 -2
2 0
1 2
-1 2
4
0 -3
1 -1
2 2
-1 0

Sample Output

5.233

HINT

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

Source

【思路】

　　半平面交即若干个直线代表的半平面的重合部分。

【代码】

 #include<cmath>

 #include<cstdio>

 #include<vector>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int eps = 1e-;

 struct Pt {

     double x,y;

     Pt (double x=,double y=) :x(x),y(y) {}

 };

 typedef Pt vec;

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

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

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

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

 struct Line {

     Pt p; vec v; double ang;

     Line() {}

     Line(Pt p,vec v) :p(p),v(v) { ang=atan2(v.y,v.x); }

     bool operator < (const Line& rhs) const {

         return ang < rhs.ang;

     }

 };

 bool onleft(Line L,Pt p) { return cross(L.v,p-L.p)>; }

 Pt getLineInter(Line a,Line b) {

     vec u=a.p-b.p;

     double t=cross(b.v,u)/cross(a.v,b.v);

     return a.p+a.v*t;

 }

 vector<Pt> HPI(vector<Line> L) {

     int n=L.size();

     sort(L.begin(),L.end());

     int f,r;

     vector<Pt> p(n) , ans;

     vector<Line> q(n);

     q[f=r=]=L[];

     for(int i=;i<n;i++) {

         while(f<r && !onleft(L[i],p[r-])) r--;

         while(f<r && !onleft(L[i],p[f])) f++;

         q[++r]=L[i];

         if(fabs(cross(q[r].v,q[r-].v))<eps) {

             r--;

             if(onleft(q[r],L[i].p)) q[r]=L[i];

         }

         if(f<r) p[r-]=getLineInter(q[r-],q[r]);

     }

     while(f<r && !onleft(q[f],p[r-])) r--;

     if(r-f<=) return ans;

     p[r]=getLineInter(q[r],q[f]);

     for(int i=f;i<=r;i++) ans.push_back(p[i]);

     return ans;

 }

 vector<Line> L;

 vector<Pt> p;

 Pt t[];

 int n,m;

 int main() {

     scanf("%d",&n);

     for(int i=;i<n;i++) {

         scanf("%d",&m);

         for(int i=;i<m;i++)

             scanf("%lf%lf",&t[i].x,&t[i].y);

         for(int i=;i<m;i++)

             L.push_back(Line(t[i-],t[i]-t[i-]));

         L.push_back(Line(t[m-],t[]-t[m-]));

     }

     p = HPI(L);

     double ans=0.0; int m=p.size();

     for(int i=;i<m-;i++)

         ans += cross(p[i]-p[],p[i+]-p[]);

     printf("%.3lf",ans/);

     return ;

 }

秒客网