分数: 300 点
问题陈述
有 N 坐标平面中的城镇。镇 i 位于坐标 (x_i, y_i)。城镇之间的距离 i 和镇 j is \sqrt{\left(x_i-x_j\right)^2+\left(y_i-y_j\right)^2}.
有 N! 访问所有这些城镇一次的可能路径。设路径的长度为我们从路径中的第一个城镇出发,访问第二个、第三个、 \dots,城镇,并到达最后一个城镇(假设我们从一个城镇直线行驶到另一个城镇)。计算这些的平均长度 N! 路径。
约束
- 2 \leq N \leq 8
- -1000 \leq x_i \leq 1000
- -1000 \leq y_i \leq 1000
- \left(x_i, y_i\right) \neq \left(x_j, y_j\right) (如果 i \neq j)
- (日本标准时间 21:12 添加)输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N x_1 y_1 : x_N y_N
输出
打印路径的平均长度。 当你的输出与法官输出的绝对差值最多为时,你的输出将被判定为正确 10^{-6}.
示例输入 1
3 0 0 1 0 0 1
示例输出 1
2.2761423749
参观城镇有六种路径: 1 → 2 → 3, 1 → 3 → 2, 2 → 1 → 3, 2 → 3 → 1, 3 → 1 → 2,和 3 → 2 → 1.
路径的长度 1 → 2 → 3 is \sqrt{\left(0-1\right)^2+\left(0-0\right)^2} + \sqrt{\left(1-0\right)^2+\left(0-1\right)^2} = 1+\sqrt{2}.
通过这种方式计算其他路径的长度,我们可以看到所有路径的平均长度为:
\frac{\left(1+\sqrt{2}\right)+\left(1+\sqrt{2}\right)+\left(2\right)+\left(1+\sqrt{2}\right)+\left(2\right)+\left(1+\sqrt{2}\right)}{6} = 2.276142...
示例输入 2
2 -879 981 -866 890
示例输出 2
91.9238815543
游览城镇有两条路径: 1 → 2 和 2 → 1。这些路径具有相同的长度。
示例输入 3
8 -406 10 512 859 494 362 -955 -475 128 553 -986 -885 763 77 449 310
示例输出 3
7641.9817824387