[Usaco2006 Oct]Building the Moat护城河的挖掘

为了防止口渴的食蚁兽进入农场，Farmer John 决定在农场周围挖一条封闭的护城河。

农场中共有 $N$ 股泉水。护城河由若干条线段首尾相连构成，每条线段连接护城河上相邻的两股泉水。护城河必须包围所有泉水，即每股泉水都位于护城河内部或恰好位于护城河上。

挖掘护城河的代价很高，因此 Farmer John 希望护城河的总长度尽可能小。请计算满足上述条件的护城河的最短总长度。

每股泉水都位于一个唯一的整点坐标上，且任意 $3$ 股泉水均不共线。

输入格式

第一行包含一个整数 $N$，表示泉水的数量。

接下来 $N$ 行，每行包含两个以空格分隔的整数 $x_i$ 和 $y_i$，表示第 $i$ 股泉水的坐标。

输出格式

输出一个实数，表示满足条件的护城河的最短总长度，结果保留小数点后 $2$ 位。

样例输入

20
2 10
3 7
22 15
12 11
20 3
28 9
1 12
9 3
14 14
25 6
8 1
25 1
28 4
24 12
4 15
13 5
26 5
21 11
24 4
1 8

样例输出

70.87

样例解释

样例中最优护城河的总长度约为 $70.8700576850888$，保留小数点后 $2$ 位后得到 $70.87$。

数据范围

• $8\le N\le 5000$；
• $1\le x_i,y_i\le 10^7$；
• 所有泉水的坐标互不相同；
• 任意 $3$ 股泉水均不在同一条直线上。

来源与许可

本题为 USACO 2006 October 试题「Building the Moat」，题面与测试数据整理自 BZOJ 1670。

样例 1

输入

20
2 10
3 7
22 15
12 11
20 3
28 9
1 12
9 3
14 14
25 6
8 1
25 1
28 4
24 12
4 15
13 5
26 5
21 11
24 4
1 8

输出

70.87