UVA534 Frogger

    • 55通过
    • 146提交
  • 题目来源 UVA 534
  • 评测方式 RemoteJudge
  • 标签
  • 难度 普及+/提高
  • 时空限制 3000ms / 0MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    题目描述 一只叫Freddy的青蛙蹲坐在湖中的一块石头上。突然他发现一只叫Fiona的青蛙在湖中的另一块石头上。Freddy想要跟Fiona约会,但由于湖水太脏,他不想游泳过去而是跳过去找Fiona。很不幸,Fiona所在的石头距离他有点远,甚至超出了他的跳跃能力。然而Freddy注意到湖中还有一些其他的石头。这些石头也许会将这个很长的跳跃距离化成若干个短的跳跃距离。我们定义“青蛙距离”为Freddy跳到Fiona那里所需要的若干次跳跃中最长的那一次。现在给你Freddy,Fiona,以及湖中其他石头的坐标,让你求出最短的“青蛙距离”。

    输入 输入有可能是多组测试数据。每组数据的第一行有一个整数n(2<=n<=200),表示湖中一共有多少块石头。接下来的n行,每一行有两个整数xi,yi(0 <= xi,yi <= 1000),表示第i块石头的坐标。第1块石头的坐标是Freddy所在的位置,第二块石头的坐标是Fiona所在的位置,其他的石头上都没有青蛙。当输入n=0的时候,程序结束。

    输出 对于每一组测试数据,先输出一行"Scenario #x",然后在下一行输出"Frog Distance = y"。其中x表示当前是第几组测试数据,y为该组数据的最小“青蛙距离”。每两组测试数据之间输出一个空行。

    题目描述

    PDF

    输入输出格式

    输入格式:

    输出格式:

    输入输出样例

    输入样例#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
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。