Programming contests

ECN selejtező programozó csapatverseny, 2014. április 27.

April 27, 2014 10:30 AM – April 27, 2014 3:30 PM

Points in Figures: Rectangles

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.

Input Specification

There will be n (≤ 10) rectangle 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.

Output Specification

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

  1. r 8.5 17.0 25.5 -8.5
  2. r 0.0 10.3 5.5 0.0
  3. r 2.5 12.5 12.5 2.5
  4. *
  5. 2.0 2.0
  6. 4.7 5.3
  7. 6.9 11.2
  8. 20.0 20.0
  9. 17.6 3.2
  10. -5.2 -7.8
  11. 9999.9 9999.9
download as text file

Output for Sample Input

  1. Point 1 is contained in figure 2
  2. Point 2 is contained in figure 2
  3. Point 2 is contained in figure 3
  4. Point 3 is contained in figure 3
  5. Point 4 is not contained in any figure
  6. Point 5 is contained in figure 1
  7. Point 6 is not contained in any figure
download as text file

Diagram of sample input figures and points

University of Debrecen; Faculty of Informatics; v. 03/01/2019