说明

本题为著名的 NPC 难题的简化版本。

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

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行两个整数 $x,y$，表示某个点的坐标。

输入中保证没有重复的两点，保证最西端和最东端都只有一个点。

输出格式

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

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

25.58

提示

题目来源

《算法导论（第二版）》 15-1