You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ABC315F] Shortcuts

题面翻译

对于平面坐标上 $n$ 个点，输出从 $1$ 走到 $n$ 的代价。两点直线距离为欧几里得距离。

正常来讲，你的路径应该为 $1 \to 2\to 3 \to \cdots \to (n-1)\to n$，你的代价即为你走过的距离。

但是你被允许跳过一些点，使路径变为 $1\to 2\to \cdots \to (x-1) \to (x+1) \to \cdots \to (n-1) \to n$，跳过的点数不限，但 $1$ 号点和 $n$ 号点不能被跳过。

跳过操作需要花费，此时你的代价为你走过的距离加跳过产生的花费。

跳过的花费如下定义：

对于整个旅途，如果你跳过 $c$ 个点，设花费为 $S$，

• $c=0$ 时 $S=0$；
• $c>0$ 时 $S=2^{c-1}$。

输出从 $1$ 走到 $n$ 的最小代价。保留6位小数。

$\text{Translate by Rain.}$

题目描述

There is a race through checkpoints $1,2,...,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:

• $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$.

输入格式

输入格式如下：

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

输出格式

输出最小代价，保留6位小数。

样例 #1

样例输入 #1

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

样例输出 #1

5.828427

样例 #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.634414

样例 #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.612384

提示

数据范围

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

Sample Explanation 1

点 $1,2,5,6$ 通过， $3,4$ 跳过。 - $1\ \rightarrow\ 2$ 移动。 $2$ 点间距离为 $\sqrt{2}$ 。 - $2\ \rightarrow\ 5$ 移动。 $2$ 点间距离为 $1$ 。 - $5\ \rightarrow\ 6$ 移动。 $2$ 点间距离为 $\sqrt{2}$ 。 - 由于跳过了2个点，故 $s\ =\ 3\ +\ 2\sqrt{2}\ \approx\ 5.828427$ 。 可以证明此时$s$ 取到最小。