# Finding Rectangles

Source : ACM ICPC Mid-Central USA 1998 |
|||

Time limit : 1 sec |
Memory limit : 32 M |

**Submitted** : 288, **Accepted** : 136

Your task is to write a program that can find all rectangles that can be formed
from a given set of points. The example input and output given below correspond
to the figures above.

**Input**

The input contains one or more point sets, followed by a line containing the
number 0 that signals the end of the file. Each point set begins with a line
containing n, the number of points, and is followed by n lines that describe
the points. Each point description contains a capital letter that is the label
of the point, then a space, the horizontal coordinate, a space, and the vertical
coordinate. Within each set, points labels occur in alphabetical order.

Note that since each point is labelled with a capital letter there can be at
most 26 points. All coordinates are nonnegative integers less than 50. Points
within a set are unique.

**Output**

The output for each point set starts with ``Point set ", followed by the
number of the point set and a colon. If there are no rectangles, `` No rectangles"
appears after the colon. If there are rectangles, they are listed starting on
the next line. A blank precedes each rectangle. Each rectangle is given by its
vertex labels, in clockwise order from the upper left, so the order is upper
left, upper right, lower right, lower left. The rectangles are listed ten per
line, except for the last line, where there may be as few as one. The rectangles
are listed in alphabetical order.

**Sample Input **

7 A 1 1 B 2 1 C 3 1 D 2 3 E 3 3 F 1 4 G 3 4 8 B 1 1 D 2 1 F 4 1 J 4 4 L 2 4 M 2 3 N 4 3 P 1 2 12 A 1 5 B 2 5 C 1 4 D 2 4 E 1 3 F 2 3 G 1 2 H 2 2 I 1 1 J 2 1 K 1 0 L 2 0 5 B 1 1 D 2 1 L 2 4 N 2 3 P 1 2 0

**Sample Output**

Point set 1: DECB FGCA Point set 2: LJFD LJNM MNFD Point set 3: ABDC ABFE ABHG ABJI ABLK CDFE CDHG CDJI CDLK EFHG EFJI EFLK GHJI GHLK IJLK Point set 4: No rectangles