2012-11-22 14:06:36Morris
[UVA][跳躍] 638 - Finding Rectangles
Finding Rectangles
| Finding Rectangles |
Consider the point sets in figures 1a, 2a, and 3a. Using only those points as vertices, figures 1b, 2b, and 3b show all the rectangles that can be formed with horizontal and vertical sides. No rectangles can be formed from the points in figure 4.
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 file 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
窮舉可能會太慢，因此直接在圖形中掃，抓兩個 x 軸看相同的 y 座標。
就算如此還是很慢，用了很多跳躍的方法。
#include <stdio.h>
#include <set>
#include <iostream>
using namespace std;
int main() {
int n, cases = 0;
int x, y, i, j, ki, kj, idx1, idx2;
char s[2];
while(scanf("%d", &n) == 1 && n) {
char g[50][50] = {}, ap[50] = {};
int next[50][50] = {}, nx[50] = {};
for(i = 0; i < n; i++) {
scanf("%s %d %d", s, &x, &y);
g[x][y] = s[0];
ap[x] = 1;
}
int xpre = 0;
for(i = 0; i < 50; i++) {
if(ap[i])
nx[xpre] = i, xpre = i;
else
continue;
int pre = 0;
for(j = 0; j < 50; j++) {
if(g[i][j]) {
next[i][pre] = j;
pre = j;
}
}
next[i][pre] = -1;
}
nx[xpre] = -1;
set<string> ans;
char buf[26][2], buft;
for(i = ap[0] == 0 ? nx[0] : 0; i != -1; i = nx[i]) {
for(j = nx[i]; j != -1; j = nx[j]) {
idx1 = 0, idx2 = 0, buft = 0;
if(!g[i][idx1]) idx1 = next[i][idx1];
if(!g[j][idx2]) idx2 = next[j][idx2];
while(idx1 != -1 && idx2 != -1) {
if(idx1 == idx2)
buf[buft][0] = g[i][idx1], buf[buft++][1] = g[j][idx2];
if(idx1 <= idx2)
idx1 = next[i][idx1];
else
idx2 = next[j][idx2];
}
for(ki = 0; ki < buft; ki++) {
for(kj = ki+1; kj < buft; kj++) {
string tmp = "";
tmp = tmp + buf[kj][0] + buf[kj][1] + buf[ki][1] + buf[ki][0];
ans.insert(tmp);
}
}
}
}
printf("Point set %d:", ++cases);
if(ans.size() == 0)
puts(" No rectangles");
else {
puts("");
int cnt = 0;
for(set<string>::iterator it = ans.begin();
it != ans.end(); it++) {
putchar(' ');
putchar((*it)[0]);
putchar((*it)[1]);
putchar((*it)[2]);
putchar((*it)[3]);
cnt++;
if(cnt == 10)
cnt = 0, puts("");
}
if(cnt)
puts("");
}
}
return 0;
}