该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

当你需要依次访问所有城镇各一次时，访问城镇的路径共有 $N!$ 种。

从第一个访问的城镇出发，依次经过第二个、第三个，$\ldots$，直到第 $N$ 个访问的城镇，每次从一个城镇到下一个城镇都按直线移动。

每条路径的长度定义为所有相邻城镇之间距离之和。

请计算所有 $N!$ 条路径长度的平均值。

输入格式

第一行输入 $N$

接下来 $N$ 行，每行输入两个整数 $x_i,y_i$。

输出格式

输出路径长度的平均值。若你的输出与标准答案的绝对误差或相对误差不超过 $10^{-6}$，则判定为正确。

你可以对答案至少保留 $6$ 位小数来使得误差尽量小一些。

3
0 0
1 0
0 1

2.2761423749

2
-879 981
-866 890

91.9238815543

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

7641.9817824387

提示

数据范围

• $2 \leq N \leq 8$
• $-1000 \leq x_i \leq 1000$
• $-1000 \leq y_i \leq 1000$
• 任意两个城镇坐标不同。所有输入均为整数

样例 1 解释

访问城镇的路径有

• $1 \to 2 \to 3$
• $1 \to 3 \to 2$
• $2 \to 1 \to 3$
• $2 \to 3 \to 1$
• $3 \to 1 \to 2$
• $3 \to 2 \to 1$

共 $6$ 种。

以路径 $1 \to 2 \to 3$ 为例，其长度为 $\sqrt{(0-1)^2+(0-0)^2} + \sqrt{(1-0)^2+(0-1)^2} = 1+\sqrt{2}$。

同理计算其他路径长度，所有路径长度的平均值为