AT_abc145_c.[ABC145C] Average Length

在坐标平面上有 $N$ 个城镇。第 $i$ 个城镇位于坐标 $(x_i, y_i)$。城镇 $i$ 和城镇 $j$ 之间的距离为 $\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$。

当你需要依次访问所有城镇各一次时，访问城镇的路径共有 $N!$ 种。从第一个访问的城镇出发，依次经过第二个、第三个，……，直到第 $N$ 个访问的城镇，每次从一个城镇到下一个城镇都按直线移动。每条路径的长度定义为所有相邻城镇之间距离之和。请计算所有 $N!$ 条路径长度的平均值。

输入按以下格式从标准输入读入。

$N$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_N$ $y_N$

输出路径长度的平均值。若你的输出与标准答案的绝对误差或相对误差不超过 $10^{-6}$，则判定为正确。

约束条件

• $2 \leq N \leq 8$
• $-1000 \leq x_i \leq 1000$
• $-1000 \leq y_i \leq 1000$
• $(x_i, y_i) \neq (x_j, y_j)$（当 $i \neq j$ 时）
• （21:12 补充）输入中的所有值均为整数。

样例解释 1

访问城镇的路径有 $1 \to 2 \to 3$、$1 \to 3 \to 2$、$2 \to 1 \to 3$、$2 \to 3 \to 1$、$3 \to 1 \to 2$、$3 \to 2 \to 1$ 共 $6$ 种。以路径 $1 \to 2 \to 3$ 为例，其长度为 $\sqrt{(0-1)^2+(0-0)^2} + \sqrt{(1-0)^2+(0-1)^2} = 1+\sqrt{2}$。同理计算其他路径长度，所有路径长度的平均值为 $\frac{(1+\sqrt{2})+(1+\sqrt{2})+(2)+(1+\sqrt{2})+(2)+(1+\sqrt{2})}{6} = 2.276142\ldots$。

样例解释 2

访问城镇的路径有 $1 \to 2$、$2 \to 1$ 共 $2$ 种，这两条路径的长度相同。