当前位置：首页 > news >正文

UVa 477 Points in Figures Rectangles and Circles

news 2026/6/13 13:21:54

题目描述

题目要求判断给定点是否在矩形或圆形的内部（边界上的点不算）。输入包含多个图形描述（矩形或圆形）和多个点坐标。输出每个点所在的图形编号（按输入顺序），若不在任何图形内则输出相应消息。

输入格式

输入包含两部分：

第一部分：若干行，每行以字符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)<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

实现方法

读取图形时，根据类型存储参数。
对于每个点，遍历所有图形，检查是否满足上述条件。
输出时注意点和图形的编号（从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//// 版权所有（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)<<endl;}}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)<<endl;}}}if(!flag)cout<<"Point "<<cases<<" is not contained in any figure"<<endl;}intmain(intargc,char*argv[]){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);}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;}