题目描述

There are $N$ towns in a coordinate plane. Town $i$ is located at coordinates ($x_i$, $y_i$). The distance between Town $i$ and Town $j$ is $\sqrt{\left(x_i-x_j\right)^2+\left(y_i-y_j\right)^2}$.

There are $N!$ possible paths to visit all of these towns once. Let the length of a path be the distance covered when we start at the first town in the path, visit the second, third, $\dots$, towns, and arrive at the last town (assume that we travel in a straight line from a town to another). Compute the average length of these $N!$ paths.

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

输入格式

输入内容按以下格式标准输入：

$N$
$x_1$ $y_1$
$:$
$x_N$ $y_N$

输出格式

打印路径的平均长度。当你的输出与法官输出的绝对差值最多为 $10^{-6}$ 时，你的输出将被判定为正确。

样例 #1

样例输入 #1

3
0 0
1 0
0 1

样例输出 #1

2.2761423749

样例 #2

样例输入 #2

2
-879 981
-866 890

样例输出 #2

91.9238815543

样例 #3

样例输入 #3

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

样例输出 #3

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$ 解释

访问城镇有六条路径： $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$ 解释

91.9238815543

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