103155: [Atcoder]ABC315 F - Shortcuts

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

问题描述

在一个坐标平面上，按照顺序通过检查点$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$。

限制条件

• 所有输入值都是整数。
• $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)$。

输入

输入从标准输入以以下格式给出：

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

输出

打印答案。如果您的输出与真实值的绝对或相对误差不超过$10^{-5}$，则被认为是正确的。

样例输入 1

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

样例输出 1

5.82842712474619009753

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

• 从检查点$1$移动到$2$。它们之间的距离为$\sqrt{2}$。
• 从检查点$2$移动到$5$。它们之间的距离为$1$。
• 从检查点$5$移动到$6$。它们之间的距离为$\sqrt{2}$。
• 跳过了两个检查点，因此施加了罚款$2$。

这样，您可以实现$s = 3 + 2\sqrt{2} \approx 5.828427$。
您无法使$s$小于这个值。

样例输入 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

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

样例输出 3

110.61238353245736230207