• [G] Go Through

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • Finally, Wodex met Zero. But Zero wore a mask, so Wodex could not see the face.

    There was a steep cliff between them. So, Wodex could not go to the other side.
    Zero said," I have two games to share with you, if you win, you can go to in front of me, but which game do you like?"
    Wodex," First one."
    Zero," OK! Later, there will appear N disks, each disk has its own coordinate, if you can go through all the disks within M (include M) steps, you will win the game. If the distance of two disks that you go through are X, it will cost you X steps."
    Suddenly, Wodex found the outermost of all disks that Wodex and his partners could go through, but the other disks that his partners could not go through because powerful energy in these disks will let them die. So, only Wodex could complete it.
    Zero," Wodex, you have three partners, but you can only choose one of them to help you. And at the beginning, you and he can choose any disk to start game, one man can choose one disk, so start now.
    Wodex learned a skill before, so he thought it can be used. Wodex can create most of his false bodies to help him to go through these disks with him together. And his false bodies can also create most of false bodies.

    So, how can Wodex and his one of partner, as well as his false bodies go through all of disks within M steps? If one person go through one of the outermost of disks, he could not go through the other disks except the outermost of disks.

    And if one person go through one of the innermost of disks, he could not go through the other disks except the innermost of disks.


  • 输入
  • First line contains two integers N (0 < N < 100) and M (0 <= M < 10,000), then N lines follow. Each line has two double number x (-1,000.000 < x < 1,000.000) and y (-1,000.000 < y < 1,000.000), means the coordinate of this disk. 0 0 means the end of the input, and do not need to output.
  • 输出
  • If Wodex and his one of partner, as well as his false bodies went through all of disks within M steps, print the distance they went through, otherwise print 'NO'. Retained four decimal places.
  • 样例输入
  • 8 15
    -2 2
    2 -2
    2 2
    -2 -2
    0 0
    1 0
    -1 0
    0 1
    0 0
  • 样例输出
  • 15.0000
  • 提示
  • 不存在三点共线
  • 来源
  • Hungar
  • 操作

显示春菜