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