题目描述题目要求判断给定点是否在矩形或圆形的内部边界上的点不算。输入包含多个图形描述矩形或圆形和多个点坐标。输出每个点所在的图形编号按输入顺序若不在任何图形内则输出相应消息。输入格式输入包含两部分第一部分若干行每行以字符r矩形或c圆形开头后跟图形参数矩形四个实数表示左上角(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 r 0.0 10.3 5.5 0.0 c -5.0 -5.0 3.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 3 Point 2 is contained in figure 3 Point 2 is contained in figure 5 Point 3 is contained in figure 5 Point 3 is contained in figure 6 Point 4 is not contained in any figure Point 5 is contained in figure 1 Point 5 is contained in figure 2 Point 6 is contained in figure 4题目分析本题的核心是判断点是否在矩形或圆形的内部边界上的点不算。矩形内点判断给定矩形左上角(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实现方法读取图形时根据类型存储参数。对于每个点遍历所有图形检查是否满足上述条件。输出时注意点和图形的编号从111开始。精度处理由于输入为实数可能包含浮点误差。判断矩形时使用严格的和比较判断圆时使用rr r * r - EPSILON其中ϵ\epsilonϵ取10−710^{-7}10−7以避免边界误判。复杂度分析n≤10n \le 10n≤10点数未知但有限总复杂度O(点数×n)O(\text{点数} \times n)O(点数×n)。代码实现// Points in Figures: Rectangles and Circles// UVa ID: 477// Verdict: Accepted// Submission Date: 2016-07-14// UVa Run Time: 0.020s//// 版权所有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)endl;}}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)endl;}}}if(!flag)coutPoint cases is not contained in any figureendl;}intmain(intargc,char*argv[]){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);}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;}