2398.cpp

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

/* This Code is Submitted by wywcgs for Problem 2398 on 2006-10-10 at 15:33:13 */
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 102400;

class Point {
public:
	int x, y, o;
	void make(int i) { o = i; scanf("%d %d", &x, &y); }
};

class UFSet {
public:
	int parent[N], sn;
	void clear(int n) { sn = n; memset(parent, -1, sizeof(parent)); }
	int find(int);
	void unionSet(int, int);
};
int UFSet::find(int x) {
	if(parent[x] == -1) return x;
	else return (parent[x] = find(parent[x]));
}
void UFSet::unionSet(int x, int y) {
	int px = find(x), py = find(y);
	if(px != py) { parent[px] = py; sn--; }
}

bool cmp1(const Point& a, const Point& b) { return a.x < b.x || (a.x == b.x && a.y < b.y); }
bool cmp2(const Point& a, const Point& b) { return a.y < b.y || (a.y == b.y && a.x < b.x); }

int main()
{
	Point p[N];
	UFSet ufs;
	int T;

	scanf("%d", &T);
	for(int t = 0; t < T; t++) {
		int n; scanf("%d", &n);
		ufs.clear(n);
		for(int i = 0; i < n; i++) p[i].make(i);
		if((n&1) || n < 4) { printf("-1\n"); continue; }
		int r = 0;
		bool can = true;
		sort(p, p+n, cmp1);
		for(int i = 0; i < n; i += 2)
			if(p[i].x != p[i+1].x) can = false;
			else { r += p[i+1].y-p[i].y; ufs.unionSet(p[i].o, p[i+1].o); }
		sort(p, p+n, cmp2);
		for(int i = 0; i < n; i += 2)
			if(p[i].y != p[i+1].y) can = false;
			else { r += p[i+1].x-p[i].x; ufs.unionSet(p[i].o, p[i+1].o); }
		if(!can || ufs.sn != 1) printf("-1\n");
		else printf("%d\n", r);
	}
	
	return 0;
}