C - 平均长度

得分：$300$ 分

问题描述

在二维坐标系统中，有 $N$ 个城镇。第 $i$ 个城镇位于坐标 ($x_i$, $y_i$) 处。城镇 $i$ 和城镇 $j$ 之间的距离为 $\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 JST 添加）输入中的所有值都是整数。

输入

输入在标准输入中按如下格式给出：

$N$

$x_1$ $y_1$

$:$

$x_N$ $y_N$

输出

输出这些路径的平均长度。 当与评测机输出的结果的差的绝对值不超过 $10^{-6}$ 时，你的输出被判定为正确。

3
0 0
1 0
0 1

2.2761423749

有六条路径可以访问这些城镇：$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...$

2
-879 981
-866 890

91.9238815543

有两条路径可以访问这些城镇：$1$ → $2$ 和 $2$ → $1$。这两条路径的长度相同。

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

7641.9817824387