UVa 638 Finding Rectangles

题目描述给定一个点集每个点有唯一的字母标签A到Z和坐标( x , y ) (x, y)(x,y)。要求找出所有由这些点作为顶点构成的边与坐标轴平行的矩形并按指定顺序输出每个矩形的四个顶点标签。如果不存在任何矩形则输出相应提示。输入格式输入包含一个或多个点集每个点集以一行整数n nnn ≤ 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 jji j i jij若y yy相同则i ii为左上角候选j jj为右上角候选k kkk j k jkj若与i ii同x xx则k kk为左下角候选再验证l lll k l klk是否与k kk同y yy且与j jj同x xx若是则构成矩形。枚举矩形使用四重循环外层i ii遍历所有点作为左上角候选。第二层j jj从i 1 i1i1开始寻找与i ii同y yy的点作为右上角候选。第三层k kk从j 1 j1j1开始寻找与i ii同x xx的点作为左下角候选。第四层l ll从k 1 k1k1开始寻找与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//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structvertex{charlabel;intx,y;booloperator(constvertexv)const{if(y!v.y)returnyv.y;elsereturnxv.x;}};intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases0,points;vertex vertices[32];while(cinpoints,points0){for(inti0;ipoints;i)cinvertices[i].labelvertices[i].xvertices[i].y;sort(vertices,verticespoints);vectorstringrectangles;for(inti0;ipoints;i)for(intji1;jpoints;j){if(vertices[i].y!vertices[j].y)continue;for(intkj1;kpoints;k){if(vertices[i].x!vertices[k].x)continue;for(intlk1;lpoints;l){if(vertices[k].y!vertices[l].y)continue;if(vertices[j].x!vertices[l].x)continue;string rectangle;rectanglevertices[i].label;rectanglevertices[j].label;rectanglevertices[l].label;rectanglevertices[k].label;rectangles.push_back(rectangle);}}}coutPoint set cases:;if(rectangles.size()0){cout No rectangles\n;continue;}cout\n;sort(rectangles.begin(),rectangles.end());for(inti0;irectangles.size();i){cout rectangles[i];if((i1)%100)cout\n;}if(rectangles.size()%10!0)cout\n;}return0;}总结本题通过枚举所有可能的点组合来寻找轴对齐矩形利用排序保证了顶点顺序和输出顺序的一致性。由于点数最多为26 2626四重循环完全可行。关键在于理解矩形顶点的坐标关系以及如何利用排序简化枚举逻辑。输出时注意格式要求每行最多10 1010个每个矩形前有空格无矩形时输出特定信息。该方法直观高效适用于此类小规模几何问题。