2013年8月5日 星期一

2013/8/5 zj c125 frogger

#include <iostream>
#include <cstdio>
#include <cmath>
#define INF -1
using namespace std;
struct p
{
double x, y;
}P[400];
double d[400][400];
double dis(int i, int j)
{
double t1 = P[i].x-P[j].x ;
double t2 = P[i].y-P[j].y ;
return sqrt( t1 * t1 + t2 * t2 );
}
int main()
{
int cnt = 0; int n;
while( scanf("%d", &n) )
{
if( n == 0 ) break;

for(int i = 0; i < n; i++)
scanf("%lf %lf", &P[i].x, &P[i].y);

for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
d[i][j] = d[j][i] = dis(i, j);

for(int k = 0; k < n; k++)
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if( d[i][j] > max(d[i][k], d[k][j])  )
d[i][j] = max(d[i][k], d[k][j]);

printf("Scenario #%d\n", ++cnt);
printf("Frog Distance = %.3f\n", d[0][1]);
}

}

沒有留言:

張貼留言