配点: 1000 点
問題文
在二维平面上
有 N 个城市,每个城市都有
它们的编号最大为 1 减去 N 。
都市 i 的坐标是 (X_i, Y_i) 和2 在两个城市之间旅行所需的时间与直线距离相同。
即城市
要移至 i 减去 j ,\sqrt{(X_i - X_j)^2 + (Y_i - Y_j)^2} 分钟。
从某个城市出发,经过所有城市一次后,需要多少分钟才能回到起点? 如果小于
制約
- 2 \leq N \leq 15
- 0 \leq X_i \leq 1000
- 0 \leq Y_i \leq 1000
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N X_1 Y_1 X_2 Y_2 : X_N Y_N
出力
请打印答案。
到达
如果绝对或相对误差为
如果在 10^{-3} ,则视为正确。
如果您选择路线
入力例 1
4 0 0 0 1 1 0 1 1
出力例 1
4.000000000000
都市 1 \to 2 \to 4 \to 3 \to 1 ,总距离约为 写入 4 。 对于
入力例 2
7 2 5 2 3 4 1 1 1 7 2 5 3 6 5
出力例 2
18.870481592668
都市 1 \to 2 \to 4 \to 3 \to 5 \to 6 \to 7 \to 1 ,总距离约为 写入 18.87 。 对于