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)<x<max⁡(x1,x2)且min⁡(y1,y2)<y<max⁡(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​)<x<max(x1​,x2​)且min(y1​,y2​)<y<max(y1​,y2​)

圆内点判断

给定圆心(xc,yc)(x_c, y_c)(xc​,yc​)和半径rrr，点(x,y)(x, y)(x,y)在圆内部（不包括边界）当且仅当：
(x−xc)2+(y−yc)2<r2 (x - x_c)^2 + (y - y_c)^2 < r^2(x−xc​)2+(y−yc​)2<r2

三角形内点判断

给定三角形三个顶点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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constdoubleEPSILON=1e-7;structpoint{doublex,y;};structfigure{chartype;point left_top,right_top,right_bottom,left_bottom;point center;doubleradius;};vector<figure>figures;intcases=0;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;boolflag=false;for(inti=0;i<figures.size();i++){if(figures[i].type=='r'){figure rect=figures[i];if(direction(rect.left_top,rect.right_top,test)>EPSILON&&direction(rect.right_top,rect.right_bottom,test)>EPSILON&&direction(rect.right_bottom,rect.left_bottom,test)>EPSILON&&direction(rect.left_bottom,rect.left_top,test)>EPSILON){flag=true;cout<<"Point "<<cases<<" is contained in figure "<<(i+1)<<'\n';}}elseif(figures[i].type=='t'){figure triangle=figures[i];if((direction(triangle.left_top,triangle.right_top,test)>EPSILON&&direction(triangle.right_top,triangle.right_bottom,test)>EPSILON&&direction(triangle.right_bottom,triangle.left_top,test)>EPSILON)||(direction(triangle.left_top,triangle.right_top,test)<-EPSILON&&direction(triangle.right_top,triangle.right_bottom,test)<-EPSILON&&direction(triangle.right_bottom,triangle.left_top,test)<-EPSILON)){flag=true;cout<<"Point "<<cases<<" is contained in figure "<<(i+1)<<'\n';}}else{figure circle=figures[i];doublerr=pow(test.x-circle.center.x,2)+pow(test.y-circle.center.y,2);if(rr<pow(circle.radius,2)-EPSILON){flag=true;cout<<"Point "<<cases<<" is contained in figure "<<(i+1)<<'\n';}}}if(!flag)cout<<"Point "<<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(cin>>input,input!='*'){if(input=='r'){doubleleft_top_x,left_top_y,right_bottom_x,right_bottom_y;cin>>left_top_x>>left_top_y>>right_bottom_x>>right_bottom_y;figure rect;rect.type='r';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(input=='t'){figure triangle;triangle.type='t';doublex,y;cin>>x>>y;triangle.left_top=(point){x,y};cin>>x>>y;triangle.right_top=(point){x,y};cin>>x>>y;triangle.right_bottom=(point){x,y};figures.push_back(triangle);}else{doublecenter_x,center_y,radius;cin>>center_x>>center_y>>radius;figure circle;circle.type='c';circle.center=(point){center_x,center_y};circle.radius=radius;figures.push_back(circle);}}string test_x,test_y;while(cin>>test_x>>test_y){if(test_x=="9999.9"&&test_y=="9999.9")break;is_contained((point){stod(test_x),stod(test_y)});}return0;}