捷径

题目描述

在坐标平面上有一个经过检查点 $1,2,\dots,N$ 的赛跑,按此顺序进行。

检查点 $i$ 的坐标为 $(X_i,Y_i)$,所有检查点的坐标互不相同。

除检查点 $1$ 和 $N$ 以外的检查点可以跳过。

但是,设跳过的检查点数为 $C$,将施加如下惩罚:

• 如果 $C \gt 0$,惩罚为 $\displaystyle 2^{C-1}$;
• 如果 $C = 0$,惩罚为 $0$。

设 $s$ 为从检查点 $1$ 到检查点 $N$ 的总移动距离(欧几里得距离)加上惩罚。

求 $s$ 能达到的最小值。

输入格式

输入按以下格式从标准输入给出。

$N$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_N$ $Y_N$

输出格式

输出答案。当输出与真实值的绝对误差或相对误差不超过 $10^{-5}$ 时,判定为正确。

样例

6
0 0
1 1
2 0
0 1
1 0
2 1

5.82842712474619009753

考虑经过检查点 $1,2,5,6$,跳过检查点 $3,4$。

从检查点 $1$ 移动到 $2$。它们之间的距离是 $\sqrt{2}$。

从检查点 $2$ 移动到 $5$。它们之间的距离是 $1$。

从检查点 $5$ 移动到 $6$。它们之间的距离是 $\sqrt{2}$。

跳过了 $2$ 个检查点,因此施加惩罚 $2$。

这样,可以达到 $s = 3 + 2\sqrt{2} \approx 5.828427$。

无法使 $s$ 小于该值。

10
1 8
3 7
9 4
4 9
6 1
7 5
0 0
1 3
6 8
6 4

24.63441361516795872523

10
34 24
47 60
30 31
12 97
87 93
64 46
82 50
14 7
17 24
3 78

110.61238353245736230207

数据范围

• 输入中的所有值均为整数。
• $2 \le N \le 10^4$
• $0 \le X_i,Y_i \le 10^4$
• 如果 $i \neq j$,则 $(X_i,Y_i) \neq (X_j,Y_j)$。