• [1334] A Bite of China

  • 时间限制: 3000 ms 内存限制: 65535 K
  • 问题描述
  • After MatRush watch <<A Bite of China>>, he want to be fatter. So he decided to eat at all the places he can eat in China.

    So MatRush found a map of China, and sign out some places that is famous for Food.
    To simplify his journey, MatRush select a place the outermost to eat. Then he choose an outermost place next by it. After he had eaten at all the places outermost, he will stop at the first place he had chosen.


    Then he will remove all the places he had eaten at from his "TO EAT LIST".

    Next step, MatRush will choose a place the outermost in his current "TO EAT LIST" and travel to it from his current place.

    Okay, let me summarize the content above: MatRush will eat at China round by round from outside to inside.

    Your task is to tell MatRush that after he had eaten at all the places, the shortest journey he will go through.

  • 输入
  • This problem contains several cases.
    The first line of each case is an integer N (1 <= N <= 1000).
    Then N line(s) followed. Each line contains two numbers xi and yi (-10000.0 <= xi, yi <= 10000.0), indicate the coordinate of ith place.
    You can assume that each three points can not form a line.
  • 输出
  • For each case, you should output the shortest journey, four decimal will be retained.
  • 样例输入
  • 8
    0 0
    1 1
    0 3
    2 1
    3 0
    2 2
    1 2
    3 3
  • 样例输出
  • 17.4142
  • 提示
  • For the sample, MatRush can start from any point in the outter loop and then eat into the inner loop, the shortest
    distance is 3 * 4 + 1 * 4 + sqrt(2).
  • 来源
  • Matrush@ZJUT
  • 操作

显示春菜