分数: 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