UVa 137 Polygons-开发者社区

题目描述

题目给出了两个凸多边形，这两个多边形可能重叠，也可能不重叠。如果它们重叠，重叠的程度和方式也会有所不同。要求编写一个程序，读取两个凸多边形的顶点坐标（按顺时针顺序给出），并计算这两个多边形面积的“异或”（exclusive or \texttt{exclusive or}exclusive or）面积，即只属于其中一个多边形所包围的区域面积。所求面积在题目提供的示意图中已用阴影标出。

输入格式

输入由多组数据组成，每组数据包含两行：

第一行：第一个多边形的顶点数n nn，随后是n nn对整数，表示按顺时针顺序的顶点坐标( x , y ) (x, y)(x,y)。
第二行：第二个多边形的顶点数m mm，随后是m mm对整数，表示按顺时针顺序的顶点坐标( x , y ) (x, y)(x,y)。

所有坐标均为小于100 100100的正整数。输入以一行单独的0 00结束。

输出格式

对于每组数据，输出所求面积，格式为8 88位宽、保留2 22位小数的字段。所有结果在一行内输出，字段间用空格分隔。

样例输入

3 5 5 8 1 2 3 3 5 5 8 1 2 3 4 1 2 1 4 5 4 5 2 6 6 3 8 2 8 1 4 1 4 2 5 3 0

样例输出

␣␣␣␣0.00␣␣␣13.50

（注：样例输出中的空格用⊔ \sqcup⊔表示）

题目分析与解题思路

问题转化

两个多边形A AA和B BB的“异或”面积可以表示为：
X O R A r e a = A r e a ( A ) + A r e a ( B ) − 2 × A r e a ( A ∩ B ) XOR_{Area} = Area(A) + Area(B) - 2 \times Area(A \cap B)XORArea=Area(A)+Area(B)−2×Area(A∩B)
其中：

A r e a ( A ) Area(A)Area(A)和A r e a ( B ) Area(B)Area(B)分别表示两个多边形的面积。
A r e a ( A ∩ B ) Area(A \cap B)Area(A∩B)表示两个多边形的交集面积。

因此，问题的关键在于计算两个凸多边形的交集面积。

计算凸多边形交集

两个凸多边形的交集仍然是一个凸多边形（可能为空）。我们可以使用半平面交（Half-plane Intersection \texttt{Half-plane Intersection}Half-plane Intersection）的方法来求交集：

将多边形视为一组半平面：
- 对于凸多边形的每条边，将其视为一个有向线段，方向为多边形顶点的顺时针顺序。
- 该有向线段左侧（即多边形内部）的区域构成一个半平面。
构建半平面集合：
- 将多边形A AA的每条边对应的半平面加入集合。
- 将多边形B BB的每条边对应的半平面加入集合。
求半平面交：
- 使用排序增量法求所有半平面的交集，得到一个新的凸多边形（交集多边形）。
- 如果交集为空，则面积为0 00。
计算面积：
- 使用叉积法（Shoelace Formula \texttt{Shoelace Formula}Shoelace Formula）计算多边形面积。

算法步骤

读取两个多边形的顶点坐标，构建多边形对象。
分别计算两个多边形的面积。
构建两个多边形的半平面集合。
求半平面交，得到交集多边形。
计算交集多边形面积。
代入公式计算异或面积并输出。

关键点

由于输入坐标是整数，计算过程中需使用浮点数以保证精度。
注意处理精度误差，例如使用EPSILON = 1 × 10 − 7 \texttt{EPSILON} = 1 \times 10^{-7}EPSILON=1×10−7进行比较。
输出格式要求8 88位宽、保留2 22位小数，需使用setw(8)和setprecision(2)进行控制。

复杂度分析

设两个多边形的总边数为N NN，则半平面交算法的时间复杂度为O ( N log ⁡ N ) O(N \log N)O(NlogN)，空间复杂度为O ( N ) O(N)O(N)。
由于顶点数不超过100 100100，该算法可以高效运行。

代码实现

// Polygons// UVa ID: 137// Verdict: Accepted// Submission Date: 2017-12-20// UVa Run Time: 0.000s//// 版权所有（C）2016 - 2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAXV=1100;constdoubleEPSILON=1E-7;structpoint{doublex,y;point(doublex=0,doubley=0):x(x),y(y){}pointoperator+(point p){returnpoint(x+p.x,y+p.y);};pointoperator-(point p){returnpoint(x-p.x,y-p.y);};pointoperator*(doublek){returnpoint(x*k,y*k);};pointoperator/(doublek){returnpoint(x/k,y/k);};};typedefvector<point>polygon;doublecross(point a,point b){returna.x*b.y-a.y*b.x;}structline{point a,b;doubleangle;};doublecp(point a,point b,point c){returncross(b-a,c-a);}boolcw(point a,point b,point c){returncp(a,b,c)<-EPSILON;}boolcmpLine(line p,line q){if(fabs(p.angle-q.angle)<=EPSILON)returncw(p.a,p.b,q.a);returnp.angle<q.angle;}boolcmpAngle(line p,line q){returnfabs(p.angle-q.angle)<=EPSILON;}boolparallel(line p,line q){returnfabs((p.a.x-p.b.x)*(q.a.y-q.b.y)-(q.a.x-q.b.x)*(p.a.y-p.b.y))<=EPSILON;}pointgetIntersection(line p,line q){point p1=p.a;doublescale=((p.a.x-q.a.x)*(q.a.y-q.b.y)-(p.a.y-q.a.y)*(q.a.x-q.b.x))/((p.a.x-p.b.x)*(q.a.y-q.b.y)-(p.a.y-p.b.y)*(q.a.x-q.b.x));p1.x+=(p.b.x-p.a.x)*scale;p1.y+=(p.b.y-p.a.y)*scale;returnp1;}linepointToLine(point a,point b){line lr;lr.a=a,lr.b=b,lr.angle=atan2(b.y-a.y,b.x-a.x);returnlr;}doublearea(polygon&pg){if(pg.size()<3)return0.0;doubleA=0.0;intn=pg.size();for(inti=0,j=(i+1)%n;i<n;i++,j=(i+1)%n)A+=(pg[i].x*pg[j].y-pg[j].x*pg[i].y);returnfabs(A/2.0);}polygonhalfPlaneIntersection(line*sides,intnLine){polygon pg;line deq[MAXV];sort(sides,sides+nLine,cmpLine);nLine=unique(sides,sides+nLine,cmpAngle)-sides;intbtm=0,top=1;deq[0]=sides[0],deq[1]=sides[1];for(inti=2;i<nLine;i++){if(parallel(deq[top],deq[top-1])||parallel(deq[btm],deq[btm+1]))returnpg;while(btm<top&&cw(sides[i].a,sides[i].b,getIntersection(deq[top],deq[top-1])))top--;while(btm<top&&cw(sides[i].a,sides[i].b,getIntersection(deq[btm],deq[btm+1])))btm++;deq[++top]=sides[i];}while(btm<top&&cw(deq[btm].a,deq[btm].b,getIntersection(deq[top],deq[top-1])))top--;while(btm<top&&cw(deq[top].a,deq[top].b,getIntersection(deq[btm],deq[btm+1])))btm++;if(top<=(btm+1))returnpg;for(inti=btm;i<top;i++)pg.push_back(getIntersection(deq[i],deq[i+1]));if(btm<(top+1))pg.push_back(getIntersection(deq[btm],deq[top]));returnpg;}voidexclusiveOr(polygon&a,polygon&b){doubleareaA=area(a),areaB=area(b);line sides[MAXV];intnLine=0;for(inti=0;i<a.size()-1;i++)sides[nLine++]=pointToLine(a[i+1],a[i]);sides[nLine++]=pointToLine(a[0],a.back());for(inti=0;i<b.size()-1;i++)sides[nLine++]=pointToLine(b[i+1],b[i]);sides[nLine++]=pointToLine(b[0],b.back());polygon c=halfPlaneIntersection(sides,nLine);doublearea1=area(c);doublearea2=areaA+areaB-2*area1;cout<<fixed<<setw(8)<<setfill(' ')<<setprecision(2)<<(area2+1e-9);}intmain(){intn;doublexi,yi;while(cin>>n,n>0){polygon a,b;for(inti=1;i<=n;i++){cin>>xi>>yi;a.push_back(point(xi,yi));}cin>>n;for(inti=1;i<=n;i++){cin>>xi>>yi;b.push_back(point(xi,yi));}exclusiveOr(a,b);}cout<<'\n';return0;}