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 翻译