1811.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1811 on 2005-10-03 at 22:07:25 */ 
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define  MAX  100
#define  MAX_LINE  5000

class UFSet {
public:
	int father[MAX+1];
	void makeSet() {
		int i;
		for(i = 0; i <= MAX; i++) {
			father[i] = -1;
		}
	}
	int findFather(int x) {
		if(father[x] == -1) {
			return x;
		} else {
			return findFather(father[x]);
		}
	}
	void unionSet(int x, int y) {
		int fatherX = findFather(x);
		int fatherY = findFather(y);
		if(fatherX != fatherY) {
			father[fatherX] = fatherY;
		}
	}
};

typedef struct {
	int dotA;
	int dotB;
	double d;
} Line;

typedef struct {
	double x;
	double y;
} Point;

double distance(Point*, Point*);
int cmp(const void*, const void*);

int main()
{
	UFSet *uf = new UFSet;
	Point point[MAX+1];
	Line line[MAX_LINE+1];
	int i, j, fa, fb;
	int n, lineN;
	double total;
	
	while(scanf("%d", &n) == 1) {
		for(i = 0; i < n; i++) {
			scanf("%lf %lf", &point[i].x, &point[i].y);
		}
		lineN = 0;
		for(i = 0; i < n; i++) {
			for(j = i+1; j < n; j++) {
				line[lineN].dotA = i;
				line[lineN].dotB = j;
				line[lineN].d = distance(&point[i], &point[j]);
				lineN++;
			}
		}
		uf->makeSet();
		total = 0;
		qsort(line, lineN, sizeof(Line), cmp);
		for(i = 0; i < lineN; i++) {
			fa = uf->findFather(line[i].dotA);
			fb = uf->findFather(line[i].dotB);
			if(fa != fb) {
				total += line[i].d;
				uf->unionSet(line[i].dotA, line[i].dotB);
			}
		}
		printf("%.2lf\n", total);
	}
	
	return 0;
}

double distance(Point *a, Point *b)
{
	double d;

	d = sqrt((a->x - b->x)*(a->x - b->x) + (a->y - b->y)*(a->y - b->y));
	return d;
}

int cmp(const void *a, const void *b)
{
	Line *x = (Line*)a, *y = (Line *)b;
	
	if(x->d - y->d < 1e-3) {
		return -1;
	} else {
		return 1;
	}
}