AT_abc315_f [ABC315F] Shortcuts

[problemUrl]: https://atcoder.jp/contests/abc315/tasks/abc315_f 座標平面上でチェックポイント $ 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 $ として達成可能な最小の値を求めてください。

N/A

N/A

### 制約 - 入力は全て整数 - $ 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 $ つであり、このとき科せられるペナルティは $ 2 $ である。 以上のようにして、 $ s\ =\ 3\ +\ 2\sqrt{2}\ \approx\ 5.828427 $ を達成できます。 $ s $ をこの値より小さくすることはできません。