题目描述题目给出了两个凸多边形这两个多边形可能重叠也可能不重叠。如果它们重叠重叠的程度和方式也会有所不同。要求编写一个程序读取两个凸多边形的顶点坐标按顺时针顺序给出并计算这两个多边形面积的“异或”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)XORAreaArea(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}EPSILON1×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//// 版权所有C2016 - 2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXV1100;constdoubleEPSILON1E-7;structpoint{doublex,y;point(doublex0,doubley0):x(x),y(y){}pointoperator(point p){returnpoint(xp.x,yp.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);};};typedefvectorpointpolygon;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.angleq.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 p1p.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.aa,lr.bb,lr.angleatan2(b.y-a.y,b.x-a.x);returnlr;}doublearea(polygonpg){if(pg.size()3)return0.0;doubleA0.0;intnpg.size();for(inti0,j(i1)%n;in;i,j(i1)%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,sidesnLine,cmpLine);nLineunique(sides,sidesnLine,cmpAngle)-sides;intbtm0,top1;deq[0]sides[0],deq[1]sides[1];for(inti2;inLine;i){if(parallel(deq[top],deq[top-1])||parallel(deq[btm],deq[btm1]))returnpg;while(btmtopcw(sides[i].a,sides[i].b,getIntersection(deq[top],deq[top-1])))top--;while(btmtopcw(sides[i].a,sides[i].b,getIntersection(deq[btm],deq[btm1])))btm;deq[top]sides[i];}while(btmtopcw(deq[btm].a,deq[btm].b,getIntersection(deq[top],deq[top-1])))top--;while(btmtopcw(deq[top].a,deq[top].b,getIntersection(deq[btm],deq[btm1])))btm;if(top(btm1))returnpg;for(intibtm;itop;i)pg.push_back(getIntersection(deq[i],deq[i1]));if(btm(top1))pg.push_back(getIntersection(deq[btm],deq[top]));returnpg;}voidexclusiveOr(polygona,polygonb){doubleareaAarea(a),areaBarea(b);line sides[MAXV];intnLine0;for(inti0;ia.size()-1;i)sides[nLine]pointToLine(a[i1],a[i]);sides[nLine]pointToLine(a[0],a.back());for(inti0;ib.size()-1;i)sides[nLine]pointToLine(b[i1],b[i]);sides[nLine]pointToLine(b[0],b.back());polygon chalfPlaneIntersection(sides,nLine);doublearea1area(c);doublearea2areaAareaB-2*area1;coutfixedsetw(8)setfill( )setprecision(2)(area21e-9);}intmain(){intn;doublexi,yi;while(cinn,n0){polygon a,b;for(inti1;in;i){cinxiyi;a.push_back(point(xi,yi));}cinn;for(inti1;in;i){cinxiyi;b.push_back(point(xi,yi));}exclusiveOr(a,b);}cout\n;return0;}总结本题的关键在于将问题转化为求两个凸多边形的交集面积并利用半平面交算法高效求解。计算几何问题中需特别注意精度处理和边界条件。代码实现中使用了经典的排序增量算法求半平面交并利用叉积法计算多边形面积最终通过公式得到异或面积。该算法在时间和空间上均能满足题目要求且代码结构清晰便于理解和调试。