Shortcuts

题目描述

在坐标平面上有一条依次经过检查点 $1,2,\dots,N$ 的赛道。
检查点 $i$ 的坐标是 $(X_i,Y_i)$，且所有检查点的坐标两两不同。 除检查点 $1$ 和 $N$ 外的检查点可以被跳过。
然而，设被跳过的检查点数量为 $C$，则会施加以下惩罚：

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

设 $s$ 为从检查点 $1$ 到检查点 $N$ 的总行程（欧几里得距离）加上惩罚。
求可以达到的最小 $s$ 值。

输入格式

输入按下述格式由标准输入提供： $N$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_N$ $Y_N$

输出格式

输出答案。当输出的绝对或相对误差不超过 $10^{-5}$ 时，视为正确。

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

5.82842712474619009753

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

24.63441361516795872523

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

110.61238353245736230207

提示

所有输入值均为整数。 $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$。考虑经过检查点 $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$ 值。

标签: AtCoder|abc315F

来源

AtCoder|abc315F