Description
有一只叫做Freddy的青蛙坐在湖中央的一块石头上，突然间他发现另一只青蛙（她的名字是Fiona）坐在另一颗石头上。他想要过去找她，但是因为湖水很脏，到处充满着游客的防晒油，所以他决定用跳的，而不要用游的。 不妙的是Fiona的石头离他的距离超出他所能跳的范围。因此Freddy考虑利用其它的一些石头当作中继站，因此他就可以跳比较小的距离（或许要跳许多次）去找Fiona。要这样子连续的跳，很明显的Freddy一次能跳的距离必须至少和这一串石头间的距离最大的距离一样。因此，介于石头间的蛙跳距离（frog distance，人类也称之为minmax distance）定义为要从Freddy所在的石头要跳到Fiona所在的石头的路径中，最小必须要跳的距离。给你Freddy所在的石头、Fiona所在的石头，以及湖中所有其它石头的坐标，你的任务是算出介于Freddy和Fiona所在石头间的蛙跳距离。
Input
输入含有多组测试数据。每组测试资料的第一列有1个整数n，代表石头的数目（2 <= n <= 200）。接下来的n列每列有2个整数xi，yi（0 <= xi，yi <= 1000）代表第i颗石头的坐标。其中第一颗为Freddy所在的石头，第二颗为Fiona所在的石头，其它的n-2颗石头上则是空的。 每组测试数据后有一空白列，当n=0时代表输入结束。请参考Sample Input。
Output
对每一组测试数据，输出一列这是第几组测试数据，以及一列蛙跳距离。 每组测试数据后亦输出一空白列。请参考Sample Output。
Sample Input
2 0 0 3 4
3 17 4 19 4 18 5
0 Sample Output
Scenario #1 Frog Distance = 5.000
Scenario #2 Frog Distance = 1.414
题解：
最小生成树，但只需要求到2点的最长最短路，所以到2就退出。
代码
var
a:
array[
1..
200,
1..
200]
of real;
b:
array[
1..
200]
of longint;
c:
array[
1..
200]
of real;
d:
array[
1..
200,
1..
2]
of longint;
n,i,j,k,e,x:longint;
min,ans:real;
procedure init;
begin
for i:=
1 to n
do
begin
readln(d[i,
1],d[i,
2]);
for j:=
1 to i-
1 do
begin
a[i,j]:=sqrt(sqr(d[i,
1]-d[j,
1])+sqr(d[i,
2]-d[j,
2]));
a[j,i]:=a[i,j];
end;
end;
end;
begin
while 1=
1 do
begin
readln(n);
inc(e);
if n=
0 then exit;
init;
for i:=
1 to n
do
c[i]:=a[
1,i];
ans:=-maxlongint;
for k:=
1 to n-
1 do
begin
min:=maxlongint;
for i:=
1 to n
do
if (c[i]<min)
and(c[i]<>
0)
then
begin
min:=c[i];
x:=i;
end;
if ans<min
then ans:=min;
c[x]:=
0;
if x=
1 then break;
for i:=
1 to n
do
if a[i,x]<c[i]
then
begin
c[i]:=a[i,x];
b[i]:=x;
end;
if c[
2]=
0 then break;
end;
writeln(
'Scenario #',e);
writeln(
'Frog Distance = ',ans:
0:
3);
writeln;
end;
end.
转载请注明原文地址: https://ju.6miu.com/read-968237.html
