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}$ 时，将被判定为正确。

输入输出样例 #1

输入 #1

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

输出 #1

5.82842712474619009753

输入输出样例 #2

输入 #2

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

输出 #2

24.63441361516795872523

输入输出样例 #3

输入 #3

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

输出 #3

110.61238353245736230207

说明/提示

限制条件

• 所有输入均为整数。
• $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 翻译