UVa 534 - Frogger

// UVa 534 - Frogger

#include <iostream>
#include <cmath>
#include <queue>
#include <string.h>
#include <stdio.h>
using namespace std;

struct point {
	double x, y;
};

struct edge {
	int i, j;
	double d;
};

bool operator <(edge a, edge b) {
	return a.d > b.d;
}

double dist(point p1, point p2) {
	return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}

int main() {
	int n, t = 0;
	while (cin >> n && n) {
		t++;
		point rock[200];
		int from[200];
		double dst[200];
		for (int i = 0; i < n; i++)
			cin >> rock[i].x >> rock[i].y;
		priority_queue<edge> q;
		for (int i = 1; i < n; i++) {
			edge e = { 0, i, dist(rock[0], rock[i]) };
			q.push(e);
		}
		bool yet[200];
		memset(yet, true, sizeof(yet));
		yet[0] = false;
		while (yet[1]) {
			edge e;
			do {
				e = q.top();
				q.pop();
			} while (!yet[e.j]);
			from[e.j] = e.i;
			dst[e.j] = e.d;
			yet[e.j] = false;
			for (int i = 1; i < n; i++)
				if (yet[i]) {
					edge f = { e.j, i, dist(rock[e.j], rock[i]) };
					q.push(f);
				}
		}
		double sol = 0;
		int i = 1;
		while (i) {
			sol = max(sol, dst[i]);
			i = from[i];
		}
		printf("Scenario #%d\n", t);
		printf("Frog Distance = %.3f\n", sqrt(sol));
		printf("\n");
	}
	return 0;
}