题目描述

在二维坐标系统中，有 $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!$ 条路径的平均长度。

输入

第一行为一个整数,表示城镇的数量

接下来一共有$N$行，表示第$i$个城市的坐标$x_i,y_i$。

输出

输出这些路径的平均长度。 当与评测机输出的结果的差的绝对值不超过$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

提示

• $2\ <\ =\ N\ <\ =\ 8$
• $-1000\ <\ =\ x_i\ <\ =\ 1000$
• $-1000\ <\ =\ y_i\ <\ =\ 1000$
• $ \left(x_i,\ y_i\right)\ \neq\ \left(x_j,\ y_j\right) $ ( 若$i\ \neq\ j$ )
• 输入中的所有值都是整数。