AT_abc315_f.[ABC315F] Shortcuts

在坐标平面上进行一场比赛，参赛者需要依次经过检查点 $1,2,\dots,N$。
第 $i$ 个检查点的坐标为 $(X_i, Y_i)$，所有检查点的坐标均不相同。

除了检查点 $1$ 和 $N$ 之外，其余检查点可以选择跳过不经过。
设未经过的检查点数量为 $C$，将根据以下规则对参赛者进行惩罚：

• 若 $C > 0$，则惩罚为 $2^{C-1}$。
• 若 $C = 0$，则惩罚为 $0$。

从检查点 $1$ 到检查点 $N$ 的总移动距离（欧几里得距离）与惩罚之和记为 $s$。
请你求出 $s$ 可能取得的最小值。

输入以如下格式从标准输入读入：

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

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

限制条件

• 所有输入均为整数。
• $2 \leq N \leq 10^4$。
• $0 \leq X_i, Y_i \leq 10^4$。
• 若 $i \neq j$，则 $(X_i, Y_i) \neq (X_j, Y_j)$。

样例解释 1

考虑经过检查点 $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$。

由 ChatGPT 4.1 翻译