站外题求助qwq

蛙跳

暂无标签

时间限制：C/C++ 200MS，其他语言 400MS 内存限制：C/C++ 16MB，其他语言 32MB 难度：中等 分数：100 OI排行榜得分：12(0.1分数+2难度) 作者：

描述

湖中有 n 块石头（编号 1,2,...,n），坐在 1 号石头上的青蛙 Freddy 发现 Fiona 在 2 号石头上，Freddy 想过去找 Fiona 。但他不想游过去找她，因为湖水太脏了，湖面上漂浮着游客留下的各种垃圾。

所以，他想通过在石头间跳跃，跳到 2 号石头上。他想知道：他的跳远（单次跳跃）能力的最小值？

输入描述

包含多组数据（不超过 10 组），对于每组数据：

第 1 行，包含 1 个整数 n，代表湖中石头块数 接下来 n 行，为 1,2,...,n 号石头的坐标，每行包含 2 个整数 x i ​ ,y i ​ ，代表一块石头的坐标 【测试数据范围】2≤n≤200，0≤x i ​ ,y i ​ ≤1000

输出描述

对于每组数据，输出 3 行：

第 1 行，输出一个字符串 Scenario #x 其中 x 为一个整数，代表数据组号（ 从 1 开始 ） 第 2 行，输出一个字符串 Frog Distance = y 其中 y 为一个保留小数点后 3 位的实数，代表答案 第 3 行，空一行 用例输入 1

2

0 0

3 4

3

17 4

21 4

18 5

用例输出 1

Scenario #1

Frog Distance = 5.000

Scenario #2

Frog Distance = 3.162 提示

【样例解释】

对于第 1 组数据，只有一种路线：

只能从 1 号直接跳到 2 号石头，两者距离为
(3−0) 2 +(4−0) 2

​ =5 因此，他跳远能力的最小值为 5

对于第 2 组数据，有两种路线：

从 1 号直接跳到 2 号石头，两者距离为
(21−17) 2 +(4−4) 2

​ =4 先从 1 号跳到 3 号（ 两者距离为
(18−17) 2 +(5−4) 2

​ =1.414 ），再从 3 号跳到 2 号（ 两者距离为
(21−18) 2 +(4−5) 2

​ =3.162 ） 因此，选择第 2 种路线，他跳远能力的最小值为 max(1.414,3.162)=3.162