Frogger

题意翻译

### 题目描述 一只叫 Freddy 的青蛙蹲坐在湖中的一块石头上,突然他发现一只叫 Fiona 的青蛙在湖中的另一块石头上。 Freddy 想要跟 Fiona 约会,但由于湖水太脏,他不想游泳过去而是跳过去找 Fiona。很不幸,Fiona 所在的石头距离他有点远,甚至超出了他的跳跃能力。然而 Freddy 注意到湖中还有一些其他的石头。这些石头也许会将这个很长的跳跃距离化成若干个短的跳跃距离。我们定义“青蛙距离”为 Freddy 跳到 Fiona 那里所需要的若干次跳跃中最长的那一次。 现在给你 Freddy,Fiona,以及湖中其他石头的坐标,让你求出最短的“青蛙距离”。 ### 输入格式 **本题有多组数据**。 每组数据的第一行有一个整数 $n$,表示湖中一共有多少块石头。 接下来的 $n$ 行,每一行有两个整数 $x_i,y_i$,表示第 $i$ 块石头的坐标。第 $1$ 块石头的坐标是 Freddy 所在的位置,第 $2$ 块石头的坐标是 Fiona 所在的位置,其他的石头上都没有青蛙。 当输入 $n=0$ 的时候,程序结束。 保证 $2\le n\le200$,$0\le x_i,y_i\le 10^3$。 ### 输出格式 对于每一组测试数据,先输出一行 `Scenario #x`,然后在下一行输出 `Frog Distance = y`。 其中 `x` 表示当前是第几组测试数据,`y` 为该组数据的最小“青蛙距离”。 每两组测试数据之间输出一个空行。

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=475 [PDF](https://uva.onlinejudge.org/external/5/p534.pdf) ![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA534/b0bcfbfca84aa24e658436ff13c507fa93b386ab.png)

输入输出格式

输入格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA534/d54203b86f5ec7bd194f7eeaa6bc7fffb956919b.png)

输出格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA534/dd854d382407c56ca65ca2a9ba03b9c0dfc73450.png)

输入输出样例

输入样例 #1

2
0 0
3 4

3
17 4
19 4
18 5
0

输出样例 #1

Scenario #1
Frog Distance = 5.000

Scenario #2
Frog Distance = 1.414