← 返回题目列表

AtCoder · abc315_f

I. 快捷键

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

有一场通过检查站的比赛 1,2,\dots,N 在坐标平面上按此顺序。
检查点坐标 i 是 (X_i,Y_i),并且所有检查点都有不同的坐标。

检查点以外的检查点 1 和 N 可以跳过。
然而,让 C 是跳过的检查点数量,将受到以下惩罚:

  • \displaystyle 2^{C−1} if C>0,和
  • 0 if C=0.

让 s 是从检查点出发的总距离(欧氏距离) 1 前往检查点 N 加上罚款。
找到最小可实现值 s.

约束

  • 所有输入值均为整数。
  • 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.

输入

输入由标准输入按以下格式给出:

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 to 2。他们之间的距离是 \sqrt{2}.
  • 从检查点移动 2 to 5。他们之间的距离是 1.
  • 从检查点移动 5 to 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