zoj1942

大家好，又见面了，我是你们的朋友全栈君。

#include<iostream>
#include<math.h>
#include<stdio.h>
using namespace std;
double d[201][201];  //从1开始
void countD(int n);
void output(int n);
double min(double a, double b);
double max(double a, double b);


struct COR
{
	int num;
	double x, y;
}c[201];     //从1开始

int main()
{
	int i, n,t=1;
	
	while (cin >> n&&n)
	{
		for (i = 1; i <= n; i++)     //整体初始化
		{
			c[i].num = i;
			cin >> c[i].x >> c[i].y;
		}
		countD(n);
		output(n);
		cout << "Scenario #" << t << endl; t++;
		printf("Frog Distance = %.3lf\n", d[1][2]);
		//cout <<"Frog Distance = ";
		//cout.precision(4);
		//cout << d[1][2] << endl;
		cout << endl;
	}

	return 0;
}

void countD(int n)
{
	for (int i = 1; i < n; i++)
	{
		for (int j = i + 1; j <= n; j++)
		{
			d[i][j] = sqrt((c[i].x-c[j].x)*(c[i].x - c[j].x)+(c[i].y - c[j].y)*(c[i].y - c[j].y));
			d[j][i] = d[i][j];
		}
	}
}

void output(int n)
{
	int i, j, k;
	for (k = 1; k<=n; k++)
		for (i = 1; i<=n; i++)
			for (j = 1; j<=n; j++)
				d[i][j] = min(d[i][j], max(d[i][k], d[k][j]));   //若直接是自身已有的路径，则选择最短的；若需要拆分的路径，则选择当前路径最长的那一段
}

double min(double a, double b)
{
	if (a>b) return b;
	else return a;
}
double max(double a, double b)
{
	if (a>b) return a;
	else return b;
}