首页 > 代码库 > 凸多边形并 [ECNU 1624] 求交集多边形面积

凸多边形并 [ECNU 1624] 求交集多边形面积

求交集多边形面积

Time Limit:1000MS Memory Limit:30000KB Total Submit:98 Accepted:42

Description 
在平面上有两给定的凸多边形,若两凸多边形相交,则它们的交集也是一个凸多边形。若两凸多边形不相交,指的是两凸多边形相离或仅限于边界点与边上相交,则相交面积为0。如图所示: 你的任务是编程给出交集多边形的面积。 两给定的凸多边形按顺时针方向依次给出多边形每个顶点的坐标。

Input 
输入文件第一行为一整数M,表示第一个凸多边形的边数,以后M行分别给出了M个顶点的坐标;接着,给出第二个凸多边形的边数N,以后N行分别给出了N个顶点的坐标。

Output 
只一个数据即交集面积,保留两位小数点。

Sample Input 
4

0 0

0 1

1 1

1 0

4

-0.5 -0.5

-0.5 0.5

0.5 0.5

0.5 -0.5

Sample Output 
0.25

 

半平面交、不确定是不是对的、- -

#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>using namespace std;#define EPS 1e-8#define N 1010int n;int dq[N];int top,bot,pn;int dump(double x){    if(fabs(x)<EPS) return 0;    return x>0?1:-1;}struct Point{    double x,y;    Point (){}    Point (double x,double y):x(x),y(y){}    Point operator - (Point p){        return Point(x-p.x,y-p.y);    }    Point operator + (Point p){        return Point(x+p.x,y+p.y);    }    Point operator * (double d){        return Point(x*d,y*d);    }    double operator ^ (Point p){        return x*p.y-y*p.x;    }};struct Line{    Point s,e;    double k;    Line(){}    Line(Point s,Point e):s(s),e(e){        k=atan2(e.y-s.y,e.x-s.x);    }    Point operator & (Line l){               return s+(e-s)*(((l.e-l.s)^(l.s-s))/((l.e-l.s)^(e-s)));    }};Line l[N];Point p[N];bool HPIcmp(Line a,Line b){    int d=dump(a.k-b.k);    if(!d) return dump((b.s-a.s)^(b.e-a.s))>0;    return d<0;}bool Judge(Line a,Line b,Line c)  {    Point p=b&c;    return dump((a.s-p)^(a.e-p))<0;   }void HPI(int n){    int i,j;    sort(l,l+n,HPIcmp);           for(i=0,j=0;i<n;i++)      {        if(dump(l[i].k-l[j].k)>0) l[++j]=l[i];    }    n=j+1;    dq[0]=0;      dq[1]=1;    top=1;    bot=0;    for(i=2;i<n;i++)    {        while(top>bot && Judge(l[i],l[dq[top]],l[dq[top-1]])) top--;        while(top>bot && Judge(l[i],l[dq[bot]],l[dq[bot+1]])) bot++;        dq[++top]=i;    }    while(top>bot && Judge(l[dq[bot]],l[dq[top]],l[dq[top-1]])) top--;    while(top>bot && Judge(l[dq[top]],l[dq[bot]],l[dq[bot+1]])) bot++;    dq[++top]=dq[bot];    for(pn=0,i=bot;i<top;i++,pn++)    {        p[pn]=l[dq[i+1]]&l[dq[i]];    }}double GetArea(){    double marea=0;    if(pn<3) return 0;    for(int i=2;i<pn;i++)    {        marea+=(p[i]-p[0])^(p[i-1]-p[0]);    }    return fabs(marea)/2;}int main(){    int n,m,tot;    while(scanf("%d%d",&n,&m)!=EOF)    {        tot=0;        Point p1[N],p2[N];        for(int i=0;i<n;i++) scanf("%lf%lf",&p1[i].x,&p1[i].y);        for(int i=0;i<m;i++) scanf("%lf%lf",&p2[i].x,&p2[i].y);        for(int i=0;i<n;i++) l[tot++]=Line(p1[i],p1[(i-1+n)%n]);        for(int i=0;i<m;i++) l[tot++]=Line(p2[i],p2[(i-1+m)%m]);        HPI(tot);        printf("%.2f\n",GetArea());    }    return 0;}

 

凸多边形并 [ECNU 1624] 求交集多边形面积