F - Shortcuts Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

座標平面上でチェックポイント 1,2,\dots,N をこの順に通るレースが行われます。
チェックポイント i の座標は (X_i,Y_i) であり、すべてのチェックポイントの座標は異なります。

チェックポイント 1,N 以外のチェックポイントは、通過を省略することもできます。
ただし、通らなかったチェックポイントの個数を C として、以下の通りペナルティが課せられます。

  • C>0 なら \displaystyle 2^{C−1}
  • C=0 なら 0

チェックポイント 1 からチェックポイント N までの総移動距離（ユークリッド距離）とペナルティの和を s とします。
このとき、 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 \rightarrow 2 に移動する。 2 点間の距離は \sqrt{2} である。
  • チェックポイント 2 \rightarrow 5 に移動する。 2 点間の距離は 1 である。
  • チェックポイント 5 \rightarrow 6 に移動する。 2 点間の距離は \sqrt{2} である。
  • 通らなかったチェックポイントは 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

Score : 500 points

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