1832.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1832 on 2005-10-29 at 21:13:52 */ 
#include <cstdio>
#include <cstdlib>

const int MAX = 102400;

typedef struct {
	int x;
	int y;
} Post;

Post post[MAX];

int cmpX(const void*, const void*);
int cmpY(const void*, const void*);

int main()
{
	int sortX[MAX], sortY[MAX];
	int P, i;
	long long length;
	
	while(scanf("%d", &P) == 1) {
		if(P == 0) {
			return 0;
		} else {
			for(i = 0; i < P; i++) {
				scanf("%d %d", &post[i].x, &post[i].y);
				sortX[i] = sortY[i] = i;
			}
			qsort(sortX, P, sizeof(int), cmpX);
			qsort(sortY, P, sizeof(int), cmpY);
			length = 0;
			for(i = 0; i < P; i += 2) {
				length += post[sortX[i+1]].y - post[sortX[i]].y;
				length += post[sortY[i+1]].x - post[sortY[i]].x;
			}
			printf("The length of the fence will be %lld units.\n", length);
		}
	}
	
	return 0;
}

int cmpX(const void *a, const void *b)
{
	int i = *(int*)a, j = *(int*)b;
	if(post[i].x < post[j].x) {
		return -1;
	} else if(post[i].x > post[j].x) {
		return 1;
	} else {
		if(post[i].y < post[j].y) {
			return -1;
		} else {
			return 1;
		}
	}
}
int cmpY(const void *a, const void *b)
{
	int i = *(int*)a, j = *(int*)b;
	if(post[i].y < post[j].y) {
		return -1;
	} else if(post[i].y > post[j].y) {
		return 1;
	} else {
		if(post[i].x < post[j].x) {
			return -1;
		} else {
			return 1;
		}
	}
}