Score : $500$ points

问题描述

在坐标平面上有一场按顺序经过检查点 $1,2,\dots,N$ 的比赛。 检查点 $i$ 的坐标为 $(X_i,Y_i)$，所有检查点的坐标均不相同。

除了检查点 $1$ 和 $N$ 之外，其它检查点可以跳过。 但是，设跳过的检查点数量为 $C$，将会受到以下惩罚：

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

令 $s$ 为从检查点 $1$ 到检查点 $N$ 的总行驶距离（欧几里得距离）加上相应的惩罚。
请找出可达到的最小值 $s$。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There is a race through checkpoints $1,2,\dots,N$ in this order on a coordinate plane.
The coordinates of checkpoint $i$ are $(X_i,Y_i)$, and all checkpoints have different coordinates.

Checkpoints other than checkpoints $1$ and $N$ can be skipped.
However, let $C$ be the number of checkpoints skipped, and the following penalty will be imposed:

• $\displaystyle 2^{C−1}$ if $C>0$, and
• $0$ if $C=0$.

Let $s$ be the total distance traveled (Euclidean distance) from checkpoint $1$ to checkpoint $N$ plus the penalty.
Find the minimum achievable value as $s$.

Constraints

• All input values are integers.
• $2 \le N \le 10^4$
• $0 \le X_i,Y_i \le 10^4$
• $(X_i,Y_i) \neq (X_j,Y_j)$ if $i \neq j$.

Input

The input is given from Standard Input in the following format:

$N$

$X_1$ $Y_1$

$X_2$ $Y_2$

$\vdots$

$X_N$ $Y_N$

Output

Print the answer. Your output is considered correct if the absolute or relative error from the true value is at most $10^{-5}$.

Sample Input 1

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

Sample Output 1

5.82842712474619009753

Consider passing through checkpoints $1,2,5,6$ and skip checkpoints $3,4$.

• Move from checkpoint $1$ to $2$. The distance between them is $\sqrt{2}$.
• Move from checkpoint $2$ to $5$. The distance between them is $1$.
• Move from checkpoint $5$ to $6$. The distance between them is $\sqrt{2}$.
• Two checkpoints are skipped, so the penalty of $2$ is imposed.

In this way, you can achieve $s = 3 + 2\sqrt{2} \approx 5.828427$.
You cannot make $s$ smaller than this value.

Sample Input 2

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

Sample Output 2

24.63441361516795872523

Sample Input 3

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

Sample Output 3

110.61238353245736230207

update @ 2024/3/10 09:01:12