1450.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1450 on 2005-10-04 at 09:54:43 */ 
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#define  MAX  200

typedef struct {
	int stone;
	double d;
} Line;
	
typedef struct {
	Line line[MAX+1];
	int x;
	int y;
} Stone;

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

int main()
{
	Stone stone[MAX+1];
	int i, j, k, test = 1;
	int n, order, before[MAX+1], b, c;
	double min, max, d[MAX+1];
	bool jump[MAX+1];
	
	while(scanf("%d", &n) == 1) {
		if(n == 0) {
			return 0;
		} else {
			memset(jump, false, sizeof(jump));
			for(i = 0; i < n; i++) {
				scanf("%d %d", &stone[i].x, &stone[i].y);
			}
			for(i = 0; i < n; i++) {
				for(j = i; j < n; j++) {
					stone[j].line[i].stone = i;
					stone[j].line[i].d = distance(&stone[i], &stone[j]);
					stone[i].line[j].stone = j;
					stone[i].line[j].d = stone[j].line[i].d;
				}
				qsort(stone[i].line, n, sizeof(Line), cmp);
			}
			jump[1] = true;
			for(i = 0; i < n; i++) {
				min = 5000;
				for(j = 0; j < n; j++) {
					if(!jump[j]) {
						for(k = 0; k < n; k++) {
							if(jump[stone[j].line[k].stone]) {
								if(min - stone[j].line[k].d > 1e-3) {
									min = stone[j].line[k].d;
									order = stone[j].line[k].stone;
									b = j;
								}
								break;
							}
						}
					}
				}
				jump[b] = true;
				before[b] = order;
				d[b] = min;
				if(b == 0) {
					break;
				}
			}
			max = 0;
			c = 0;
			do {
				if(max - d[c] < 1e-3) {
					max = d[c];
				}
				c = before[c];
			} while(c != 1);
		}
		printf("Scenario #%d\n", test);
		test++;
		printf("Frog Distance = %.3lf\n\n", max);
	}
	
	return 0;
}

double distance(Stone *a, Stone *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;
	}
}