[UVA476]Points in Figures: Rectangles

Posted by John on 2016-01-02
Words 500 and Reading Time 3 Minutes
Viewed Times

Given a list of rectangles and a list of points in the x-y plane, determine for each point which figures (if any) contain the point.


There will be n( tex2html_wrap_inline220 ) rectangles descriptions, one per line. The first character will designate the type of figure (``r’’ for rectangle). This character will be followed by four real values designating the x-y coordinates of the upper left and lower right corners. The end of the list will be signalled by a line containing an asterisk in column one. The remaining lines will contain the x-y coordinates, one per line, of the points to be tested. The end of this list will be indicated by a point with coordinates 9999.9 9999.9; these values should not be included in the output. Points coinciding with a figure border are not considered inside.


For each point to be tested, write a message of the form:

Point i is contained in figure j

for each figure that contains that point. If the point is not contained in any figure, write a message of the form:

Point i is not contained in any figure

Points and figures should be numbered in the order in which they appear in the input.

Sample Input

r 8.5 17.0 25.5 -8.5
r 0.0 10.3 5.5 0.0
r 2.5 12.5 12.5 2.5
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

Sample Output

Point 1 is contained in figure 2
Point 2 is contained in figure 2
Point 2 is contained in figure 3
Point 3 is contained in figure 3
Point 4 is not contained in any figure
Point 5 is contained in figure 1
Point 6 is not contained in any figure
#‎include‬ <iostream>; 
#include <cstdlib>;
#include <math.h>;
#include <vector>;
using namespace std;
struct cood {
float lx;
float ly;
float rx;
float ry;
int main() {
char c = 0;
cood p;
vector<cood>; r;
while(scanf("%c",&c) == 1 && c != '*') {
float templx,temply,temprx,tempry;
scanf("%f %f %f %f", &p.lx, &p.ly, &p.rx, &p.ry);
float input1,input2;
int num = 1;
while(scanf("%f %f",&input1,&input2) == 2 ) {
if(fabs(input1-9999.9)<1e-3 && fabs(input2-9999.9)<1e-3)
bool flag = false;
for(int i = 0 ; i < r.size() ; ++i) {
if( (r[i].lx < input1 && input1 < r[i].rx) && (r[i].ly >; input2 && input2 >; r[i].ry) ) {
printf("Point %d is contained in figure %d\\n",num,i+1); flag = true;
if(!flag) printf("Point %d is not contained in any figure\\n",num);
return 0;