Problem1014-- V1014 旅行商简化版

1014: V1014 旅行商简化版

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Status] [Submit] [Creator:]

Description

著名的NPC难题的简化版本

现在笛卡尔平面上有n(n< =1000)个点，每个点的坐标为(x,y)(-2^31< x,y< 2^31，且为整数)，任意两点之间相互到达的代价为这两点的欧几里德距离，现要你编程求出最短bitonic  tour。

Input

第一行一个整数n 接下来n行，每行两个整数x,y，表示某个点的坐标。 输入中保证没有重复的两点， 保证最西端和最东端都只有一个点。

Output

一行，即最短回路的长度，保留2位小数。

Sample Input Copy 

7
0 6
1 0
2 3
5 4
6 1
7 5
8 2

Sample Output Copy 

25.58

Source/Category

《算法导论（第二版）》&nbsp 15-1  
[Submit] [Status]