寻找矩形
   

　　观察图1a，2a和3a中的点集。用这些点作为顶点，图1b,2b和3b分别显示出用水平与垂直的边形成的矩形。在图4中，不能形成任何的矩形。

　　　　　　

　　你的任务是，写一个程序，对于给定的点集，找出所有能形成的矩形。输入样例中的输出表示如图1b、2b、3b。

　　输入

　　输入文件包含一个或多个点集，之后是一行有一个0表示输入文件的结束。每个点集以一行包含整数n开始，表示点集中点的个数，接下来的n行为点集中的n个点，每个点以一个大写字母开始（为这个点的标号），然后是一个空、水平方向的坐标、一个空格和垂直坐标。在每个点集中，点的标号严格按字母顺序出现。

　　注意由于每个点以大写字母标号，因此最多有26个点。所有坐标都是小于50的非负整数，一个点集中顶点是唯一的。

　　输出

　　每一个点集的输出以``Point set "开始，接着是点集的编号和一个冒号。如果无解在冒号后输出`` No rectangles"。如果有解，在下一行列出所有矩形。每一个矩形前有一个空格，每个矩形按从左上角开始顺时针给出它的四个顶点标号。除最后一行最少可能只有一个矩形外，这些矩形按每行十个输出，并且矩形输出按字典顺序。

　　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
　 		   

 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有