UVa 478 Points in Figures Rectangles Circles and Triangles

题目描述题目要求判断给定点是否在矩形、圆形或三角形的内部边界上的点不算。输入包含多个图形描述矩形、圆形或三角形和多个点坐标。输出每个点所在的图形编号按输入顺序若不在任何图形内则输出相应消息。输入格式输入包含两部分第一部分若干行每行以字符r矩形、c圆形或t三角形开头后跟图形参数矩形四个实数表示左上角(x1,y1)(x_1, y_1)(x1​,y1​)和右下角(x2,y2)(x_2, y_2)(x2​,y2​)坐标。圆形三个实数表示圆心坐标(xc,yc)(x_c, y_c)(xc​,yc​)和半径rrr。三角形六个实数表示三个顶点的坐标。图形数量n≤10n \le 10n≤10。以一行*结束。第二部分若干行每行两个实数表示点的坐标。以9999.9 9999.9结束该点不参与判断。输出格式对于每个点输出一行若点在某个图形内部输出Point i is contained in figure j其中iii为点序号从111开始jjj为图形序号从111开始。若点在多个图形内则每个图形输出一行。若点不在任何图形内输出Point i is not contained in any figure。样例输入r 8.5 17.0 25.5 -8.5 c 20.2 7.3 5.8 t -1.0 -1.0 10.1 2.2 .4 1.4 r 0.0 10.3 5.5 0.0 c -5.0 -5.0 3.7 t 20.3 9.8 10.0 -3.2 17.5 -7.7 r 2.5 12.5 12.5 2.5 c 5.0 15.0 7.2 * 2.0 2.0 4.7 5.3 6.9 11.2 20.0 20.0 17.6 3.2 -5.2 -7.8 9999.9 9999.9输出Point 1 is contained in figure 4 Point 1 is contained in figure 9 Point 2 is contained in figure 4 Point 2 is contained in figure 7 Point 2 is contained in figure 9 Point 3 is contained in figure 7 Point 3 is contained in figure 8 Point 3 is contained in figure 9 Point 4 is not contained in any figure Point 5 is contained in figure 1 Point 5 is contained in figure 2 Point 5 is contained in figure 6 Point 5 is contained in figure 9 Point 6 is contained in figure 5 Point 6 is contained in figure 9题目分析本题的核心是判断点是否在矩形、圆形或三角形的内部边界上的点不算。矩形内点判断给定矩形左上角(x1,y1)(x_1, y_1)(x1​,y1​)和右下角(x2,y2)(x_2, y_2)(x2​,y2​)矩形的xxx范围为[min⁡(x1,x2),max⁡(x1,x2)][\min(x_1, x_2), \max(x_1, x_2)][min(x1​,x2​),max(x1​,x2​)]yyy范围为[min⁡(y1,y2),max⁡(y1,y2)][\min(y_1, y_2), \max(y_1, y_2)][min(y1​,y2​),max(y1​,y2​)]。点(x,y)(x, y)(x,y)在矩形内部不包括边界当且仅当min⁡(x1,x2)xmax⁡(x1,x2)且min⁡(y1,y2)ymax⁡(y1,y2) \min(x_1, x_2) x \max(x_1, x_2) \quad \text{且} \quad \min(y_1, y_2) y \max(y_1, y_2)min(x1​,x2​)xmax(x1​,x2​)且min(y1​,y2​)ymax(y1​,y2​)圆内点判断给定圆心(xc,yc)(x_c, y_c)(xc​,yc​)和半径rrr点(x,y)(x, y)(x,y)在圆内部不包括边界当且仅当(x−xc)2(y−yc)2r2 (x - x_c)^2 (y - y_c)^2 r^2(x−xc​)2(y−yc​)2r2三角形内点判断给定三角形三个顶点A,B,CA, B, CA,B,C点PPP在三角形内部不包括边界当且仅当PPP在三条边的同侧即三个有向面积符号相同。使用叉积方向函数判断direction(A,B,P)(B.x−A.x)×(P.y−A.y)−(P.x−A.x)×(B.y−A.y) \textit{direction}(A, B, P) (B.x - A.x) \times (P.y - A.y) - (P.x - A.x) \times (B.y - A.y)direction(A,B,P)(B.x−A.x)×(P.y−A.y)−(P.x−A.x)×(B.y−A.y)若PPP在三角形内部则direction(A,B,P)\textit{direction}(A, B, P)direction(A,B,P)、direction(B,C,P)\textit{direction}(B, C, P)direction(B,C,P)、direction(C,A,P)\textit{direction}(C, A, P)direction(C,A,P)要么全为正要么全为负。由于三角形顶点顺序可能为顺时针或逆时针取绝对值判断即可。实现方法读取图形时根据类型存储参数。对于每个点遍历所有图形检查是否满足上述条件。输出时注意点和图形的编号从111开始。精度处理由于输入为实数可能包含浮点误差。判断时使用 EPSILON或 -EPSILONϵ10−7\epsilon 10^{-7}ϵ10−7以避免边界误判。复杂度分析n≤10n \le 10n≤10点数未知但有限总复杂度O(点数×n)O(\text{点数} \times n)O(点数×n)。代码实现// Points in Figures: Rectangles, Circles, and Triangles// UVa ID: 478// Verdict: Accepted// Submission Date: 2016-07-16// UVa Run Time: 0.010s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constdoubleEPSILON1e-7;structpoint{doublex,y;};structfigure{chartype;point left_top,right_top,right_bottom,left_bottom;point center;doubleradius;};vectorfigurefigures;intcases0;doubledirection(point a,point b,point c){return(c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y);}voidis_contained(point test){cases;boolflagfalse;for(inti0;ifigures.size();i){if(figures[i].typer){figure rectfigures[i];if(direction(rect.left_top,rect.right_top,test)EPSILONdirection(rect.right_top,rect.right_bottom,test)EPSILONdirection(rect.right_bottom,rect.left_bottom,test)EPSILONdirection(rect.left_bottom,rect.left_top,test)EPSILON){flagtrue;coutPoint cases is contained in figure (i1)\n;}}elseif(figures[i].typet){figure trianglefigures[i];if((direction(triangle.left_top,triangle.right_top,test)EPSILONdirection(triangle.right_top,triangle.right_bottom,test)EPSILONdirection(triangle.right_bottom,triangle.left_top,test)EPSILON)||(direction(triangle.left_top,triangle.right_top,test)-EPSILONdirection(triangle.right_top,triangle.right_bottom,test)-EPSILONdirection(triangle.right_bottom,triangle.left_top,test)-EPSILON)){flagtrue;coutPoint cases is contained in figure (i1)\n;}}else{figure circlefigures[i];doublerrpow(test.x-circle.center.x,2)pow(test.y-circle.center.y,2);if(rrpow(circle.radius,2)-EPSILON){flagtrue;coutPoint cases is contained in figure (i1)\n;}}}if(!flag)coutPoint cases is not contained in any figure\n;}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);charinput;while(cininput,input!*){if(inputr){doubleleft_top_x,left_top_y,right_bottom_x,right_bottom_y;cinleft_top_xleft_top_yright_bottom_xright_bottom_y;figure rect;rect.typer;rect.left_top(point){left_top_x,left_top_y};rect.right_top(point){right_bottom_x,left_top_y};rect.right_bottom(point){right_bottom_x,right_bottom_y};rect.left_bottom(point){left_top_x,right_bottom_y};figures.push_back(rect);}elseif(inputt){figure triangle;triangle.typet;doublex,y;cinxy;triangle.left_top(point){x,y};cinxy;triangle.right_top(point){x,y};cinxy;triangle.right_bottom(point){x,y};figures.push_back(triangle);}else{doublecenter_x,center_y,radius;cincenter_xcenter_yradius;figure circle;circle.typec;circle.center(point){center_x,center_y};circle.radiusradius;figures.push_back(circle);}}string test_x,test_y;while(cintest_xtest_y){if(test_x9999.9test_y9999.9)break;is_contained((point){stod(test_x),stod(test_y)});}return0;}