题目描述

考虑图1a、图2a和图3a中的点集。仅使用这些点作为顶点，图1b、图2b和图3b展示了所有可以由水平边和垂直边构成的矩形。图4中的点无法构成任何矩形。

你的任务是编写一个程序，该程序能够找出从给定的点集可以构成的所有矩形。下面给出的示例输入和输出与上述图形相对应。

输入

输入包含一个或多个点集，随后是一行包含数字$0$的行，该数字表示文件结束。每个点集以包含点的数量$n$的一行开始，接着是$n$行描述这些点的行。每个点的描述包含一个作为点的标签的大写字母，然后是一个空格、横坐标、一个空格以及纵坐标。在每个点集中，点的标签按字母顺序出现。请注意，由于每个点都用一个大写字母标记，所以最多可以有$26$个点。所有坐标都是小于$50$的非负整数。一个点集中的点都是唯一的。

输出

每个点集的输出以“Point set ”开头，后面跟着点集的编号和一个冒号。如果不存在矩形，冒号后面会出现“No rectangles”。如果存在矩形，它们从下一行开始列出。每个矩形前面有一个空格。每个矩形由其顶点标签表示，从左上角开始按顺时针顺序排列，所以顺序是左上角、右上角、右下角、左下角。矩形每行列出$10$个，最后一行除外，最后一行可能少至$1$个。矩形按字母顺序列出。

输入示例

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

输出示例

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

来源

1998年美国中北部地区竞赛