平均路径

题目描述

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

访问所有这些城镇各 $1$ 次时，访问城镇的路径共有 $N!$ 种。从第 $1$ 个访问的城镇出发，经过第 $2$ 个访问的城镇、第 $3$ 个访问的城镇、$\ldots$，直到抵达第 $N$ 个访问的城镇所经过的移动距离（城镇之间的移动视为直线移动）称为该路径的长度。请计算这 $N!$ 条路径长度的平均值。

输入格式

输入按以下格式从标准输入给出：

$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$ 这 $6$ 种。

其中，路径 $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$ 这 $2$ 种，但这两条路径的长度相同。

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

7641.9817824387

数据范围

• $2 \le N \le 8$
• $-1000 \le x_i \le 1000$
• $-1000 \le y_i \le 1000$
• $\left(x_i, y_i\right) \neq \left(x_j, y_j\right)$（当 $i \neq j$ 时）
• 输入中的值均为整数。