题目描述

在一个坐标平面上有 $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!$ 条路径的平均长度。

约束条件

• $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}$ 时，你的输出被认为是正确的。

示例输入 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$ 的长度为 $\\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