问题描述

在坐标平面上有$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$
• 如果$i \neq j$，则$(x_i, y_i) \neq (x_j, y_j)$
• 输入中的所有值均为整数。

输入

输入通过标准输入给出，格式如下：

N
x_1 y_1
:
x_N y_N

输出

输出路径的平均长度，保留6位小数。

样例输入1

3
0 0
1 0
0 1

样例输出1

2.276142

共有六种访问城镇的路径：$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.923881

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

样例输入3

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

样例输出3

7641.981782