UVA – 534 – Frogger

  • Problem Statment :  UVA – 534 – Frogger
  • Type : Shortest Path, But I’ve wrote it with Floyd’s Warshall Algorithm, it’s more elegant this way XD
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string.h>
#include <stdio.h>
using namespace std;
#define S(ZZ) (ZZ)*(ZZ)
#define FOR(ii, i0, in) for((ii)=(i0); (ii)<(in); (ii)++)
#define FOR2d(ii, jj, i0, j0, in, jn) FOR(ii, i0, in) FOR(jj, j0, jn)
#define FOR3d(kk, ii, jj, k0, i0, j0, kn, in, jn) FOR(kk, k0, kn) FOR(ii, i0, in) FOR(jj, j0, jn)
typedef pair<int, int> Point;

int main() {
	int t=1, N, x1, y1, i, j, k;
	while( (cin >> N) && N) {
		vector<Point> n;
		double g[300][300];
		FOR2d(i, j, 0, 0, 300, 300)  g[i][j] = g[j][i] = 999999999L;

		while (N--) {
			cin >> x1 >> y1;
			for (int v = 0; v < n.size(); v++)
				g[v][n.size()] = g[n.size()][v] = sqrt(S(x1-n[v].first) + S(y1-n[v].second));
			n.push_back(Point(x1, y1));
		}

			FOR3d(k, i, j, 0, 0, 0, n.size(), n.size(), n.size())
				g[i][j] = min(g[i][j], max(g[i][k], g[k][j]));

		cout << "Scenario #" << t++ << endl;
		printf ("Frog Distance = %.3lf\n\n", g[0][1]);
	}
	return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: