1614.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1614 on 2005-10-09 at 02:22:55 */ 
#include <cstdio>
#include <cmath>
#include <cstdlib>
#define  DIAMETER  16.7
#define  MAX  128
#define  MAX_LINE  5120

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

typedef struct {
	double longitude;
	double latitude;
} Point;

typedef struct {
	int pointA;
	int pointB;
	double d;
} Line;
	
double distance(Point*, Point*);
int cmp(const void*, const void*);

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

double distance(Point *a, Point *b)
{
	double i, j, cosB;
	double xa, ya, za, xb, yb, zb;
	double d;
		
	i = a->longitude * M_PI / 180;
	j = a->latitude * M_PI / 180;
	cosB = cos(j);
	xa = DIAMETER * cos(i) * cosB / 2;
	ya = DIAMETER * sin(i) * cosB / 2;
	za = DIAMETER * sin(j) / 2;
	i = b->longitude * M_PI / 180;
	j = b->latitude * M_PI / 180;
	cosB = cos(j);
	xb = DIAMETER * cos(i) * cosB / 2;
	yb = DIAMETER * sin(i) * cosB / 2;
	zb = DIAMETER * sin(j) / 2;
	d = sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb)+(za-zb)*(za-zb));
	if(fabs(d) < 1e-3) {
		return 0;
	} else if(fabs(d-DIAMETER) < 1e-3) {
		return DIAMETER * M_PI / 2;
	} else {
		return DIAMETER * asin(d/DIAMETER);
	}
}
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;
	}
}