UVa 638 Finding Rectangles
题目描述
给定一个点集，每个点有唯一的字母标签（A到Z）和坐标( x , y ) (x, y)(x,y)。要求找出所有由这些点作为顶点构成的边与坐标轴平行的矩形，并按指定顺序输出每个矩形的四个顶点标签。如果不存在任何矩形，则输出相应提示。
输入格式
输入包含一个或多个点集，每个点集以一行整数n nn（n ≤ 26 n \le 26n≤26）开始，表示点数。随后n nn行，每行描述一个点：一个字母标签、一个空格、横坐标x xx、一个空格、纵坐标y yy。点集内标签按字母顺序给出。所有坐标均为小于50 5050的非负整数，点不重复。输入以一行单独的数字0结束。
输出格式
对于每个点集，输出一行Point set X:，其中X XX为点集编号（从1 11开始）。如果无矩形，则在该行后直接输出No rectangles。否则，从下一行开始列出所有矩形，每个矩形前有一个空格。每个矩形用其四个顶点标签表示，顺序为顺时针：左上、右上、右下、左下。矩形按字典序（字符串比较）升序排列，每行最多输出10 1010个矩形，最后一行可以少于10 1010个。
样例
输入
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题目分析
本题要求从点集中找出所有轴对齐矩形。矩形的边必须与坐标轴平行，因此四个顶点可以描述为：
- 左上角( x 1 , y 1 ) (x_1, y_1)(x1,y1)
- 右上角( x 2 , y 1 ) (x_2, y_1)(x2,y1)（x 2 > x 1 x_2 > x_1x2>x1）
- 右下角( x 2 , y 2 ) (x_2, y_2)(x2,y2)（y 2 < y 1 y_2 < y_1y2<y1）
- 左下角( x 1 , y 2 ) (x_1, y_2)(x1,y2)
也就是说，任意一个矩形由两组不同的x xx坐标和两组不同的y yy坐标确定，且对应的四个交点都必须存在于点集中。
由于最多只有26 2626个点，可以直接枚举所有可能的点组合，检查是否构成矩形。为了按题目要求的顺序输出（左上、右上、右下、左下），可以按纵坐标降序、横坐标升序排列点，然后枚举上边的两个点（同y yy），再枚举左侧的点（与左上角同x xx），最后验证右下角是否存在。
解题思路
排序：将点按纵坐标y yy降序排列，若y yy相同则按横坐标x xx升序排列。这样在枚举时，i ii和j jj（i < j i < ji<j）若y yy相同，则i ii为左上角候选，j jj为右上角候选；k kk（k > j k > jk>j）若与i ii同x xx，则k kk为左下角候选；再验证l ll（l > k l > kl>k）是否与k kk同y yy且与j jj同x xx，若是，则构成矩形。
枚举矩形：使用四重循环：
- 外层i ii遍历所有点作为左上角候选。
- 第二层j jj从i + 1 i+1i+1开始，寻找与i ii同y yy的点作为右上角候选。
- 第三层k kk从j + 1 j+1j+1开始，寻找与i ii同x xx的点作为左下角候选。
- 第四层l ll从k + 1 k+1k+1开始，寻找与k kk同y yy且与j jj同x xx的点作为右下角候选。
- 若找到，则四个顶点顺序为：左上（i ii）、右上（j jj）、右下（l ll）、左下（k kk），将其标签拼接成字符串，存入结果列表。
排序与输出：将所有矩形字符串按字典序排序，然后按每行最多10 1010个输出，每个矩形前有一个空格。若结果为空，则输出
No rectangles。
复杂度分析
- 设点数为n ≤ 26 n \le 26n≤26，四重循环最坏情况为O ( n 4 ) O(n^4)O(n4)，即26 4 ≈ 456 , 976 26^4 \approx 456,976264≈456,976，常数很小，完全可行。
- 排序结果列表O ( m log m ) O(m \log m)O(mlogm)，其中m mm为矩形数量，最多C 26 2 ⋅ C 26 2 C_{26}^2 \cdot C_{26}^2C262⋅C262但实际远小于此。
- 空间复杂度O ( m ) O(m)O(m)。
代码实现
// Finding Rectangles// UVa ID: 638// Verdict: Accepted// Submission Date: 2017-05-31// UVa Run Time: 0.030s//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structvertex{charlabel;intx,y;booloperator<(constvertex&v)const{if(y!=v.y)returny>v.y;elsereturnx<v.x;}};intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases=0,points;vertex vertices[32];while(cin>>points,points>0){for(inti=0;i<points;i++)cin>>vertices[i].label>>vertices[i].x>>vertices[i].y;sort(vertices,vertices+points);vector<string>rectangles;for(inti=0;i<points;i++)for(intj=i+1;j<points;j++){if(vertices[i].y!=vertices[j].y)continue;for(intk=j+1;k<points;k++){if(vertices[i].x!=vertices[k].x)continue;for(intl=k+1;l<points;l++){if(vertices[k].y!=vertices[l].y)continue;if(vertices[j].x!=vertices[l].x)continue;string rectangle;rectangle+=vertices[i].label;rectangle+=vertices[j].label;rectangle+=vertices[l].label;rectangle+=vertices[k].label;rectangles.push_back(rectangle);}}}cout<<"Point set "<<++cases<<":";if(rectangles.size()==0){cout<<" No rectangles\n";continue;}cout<<'\n';sort(rectangles.begin(),rectangles.end());for(inti=0;i<rectangles.size();i++){cout<<' '<<rectangles[i];if((i+1)%10==0)cout<<'\n';}if(rectangles.size()%10!=0)cout<<'\n';}return0;}总结
本题通过枚举所有可能的点组合来寻找轴对齐矩形，利用排序保证了顶点顺序和输出顺序的一致性。由于点数最多为26 2626，四重循环完全可行。关键在于理解矩形顶点的坐标关系以及如何利用排序简化枚举逻辑。输出时注意格式要求（每行最多10 1010个，每个矩形前有空格，无矩形时输出特定信息）。该方法直观高效，适用于此类小规模几何问题。