Average Length

题目描述

在坐标平面上有 $N$$个城镇。城镇$i$位于坐标$(x_i, y_i)$。城镇$i$和城镇$j$之间的距离是$\sqrt{\left(x_i-x_j\right)^2+\left(y_i-y_j\right)^2}$。 共有$N!$种可能的路径可以一次访问所有这些城镇。设一条路径的长度为当我们从路径中的第一个城镇出发，依次访问第二个、第三个、……、城镇，并到达最后一个城镇时所行驶的距离（假设我们在城镇之间直线行驶）。计算这$N!$ 条路径的平均长度。

输入格式

输入由标准输入提供，格式如下： $N$ $x_1$ $y_1$ : $x_N$ $y_N$

输出格式

输出路径的平均长度。 当你的输出与裁判的输出的绝对差不超过 $10^{-6}$ 时，将被判定为正确。

3
0 0
1 0
0 1

2.2761423749

2
-879 981
-866 890

91.9238815543

8
-406 10
512 859
494 362
-955 -475
128 553
-986 -885
763 77
449 310

7641.9817824387

提示

$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 JST 添加）输入中的所有值均为整数。共有六条路径可以访问这些城镇：$1$ → $2$ → $3$，$1$ → $3$ → $2$，$2$ → $1$ → $3$，$2$ → $3$ → $1$，$3$ → $1$ → $2$，和 $3$ → $2$ → $1$。 路径 $1$ → $2$ → $3$ 的长度是 $\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...$
有两条路径可以访问这些城镇：$1$ → $2$ 和 $2$ → $1$。这两条路径的长度相同。

标签: AtCoder|abc145C

来源

AtCoder|abc145C