• [D] Chihuo II - Eating in China

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • After Tianyi finishing her plan of keeping weight, she decided to eat at all the places she can eat in China.
    So Tianyi found a Chinese Map, and sign out some places that is famous for FOOD.
    To simplify her journey, Tianyi select a place the outermost to eat. Then she choose an outermost place next by it. After she had eaten at all the places outermost, she will stop at the first place she had chosen.
    Then she will remove all the places she had eaten at from her "TO EAT LIST".
    Next step, Tianyi will choose a place the outermost in her current "TO EAT LIST" and travel to it from her current place.

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

    Your task is to tell Tianyi that after she had eaten at all the places, the shortest journey she 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
    
  • 提示
  • 来源
  • XadillaX
  • 操作

显示春菜