1085.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1085 on 2005-12-11 at 21:50:31 */ 
#include <cstdio>
#include <cstring>
#include <cstdlib>

const int MAX = 32;
const int LIMIT = 64;
const int ALL = 16000;

class Point {
public:
	int x, y;
	char label;
};

int cmp(const void*, const void*);

int main()
{
	Point point[MAX];
	char map[LIMIT][LIMIT];
	char rec[ALL][8];
	int n, t, rn;
	int i, j, k;
	
	for(t = 1; scanf("%d", &n) != EOF && n != 0; t++) {
		memset(map, 0, sizeof(map));
		for(i = 0; i < n; i++) {
			scanf("\n%c %d %d", &point[i].label, &point[i].y, &point[i].x);
			point[i].x = LIMIT - 1 - point[i].x;
			map[point[i].x][point[i].y] = point[i].label;
		}
		rn = 0;
		for(i = 0; i < n; i++) {
			rec[rn][0] = point[i].label;
			for(j = point[i].y+1; j < LIMIT; j++) {
				if(map[point[i].x][j] != 0) {
					rec[rn][1] = map[point[i].x][j];
					for(k = point[i].x+1; k < LIMIT; k++) {
						if(map[k][j] != 0 && map[k][point[i].y] != 0) {
							rec[rn][2] = map[k][j];
							rec[rn][3] = map[k][point[i].y];
							rec[rn][4] = 0;
							rn++;
							rec[rn][0] = point[i].label;
							rec[rn][1] = map[point[i].x][j];
						}
					}
				}
			}
		}
		printf("Point set %d:", t);
		if(rn == 0) {
			printf(" No rectangles\n");
		} else {
			qsort(rec, rn, sizeof(rec[0]), cmp);
			for(i = 0; i < rn; i++) {
				if(i % 10 == 0) {
					putchar('\n');
				}
				printf(" %s", rec[i]);
			}
			putchar('\n');
		}
	}
	
	return 0;
}

int cmp(const void* a, const void* b)
{
	char *x = (char*)a, *y = (char*)b;
	return strcmp(x, y);
}