环城旅行

题目背景

Y 同学正在计划一次完美的环城旅行，他希望参观分布在二维平面上的 $N$ 个风景优美的城镇。在出发前，他想对所有可能的旅行路线的平均长度有一个大致的了解，以便更好地规划预算和时间。

题目描述

在二维坐标平面上，分布着 $N$ 个城镇，第 $i$ 个城镇的坐标为 $(x_i, y_i)$。城镇 $i$ 和城镇 $j$ 之间的直线距离定义为欧几里得距离：$\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}$。

Y 同学计划依次访问所有 $N$ 个城镇，每个城镇仅访问一次。这样的一条完整访问路线共有 $N!$ 种（即对城镇编号 $1, \dots, N$ 的所有排列）。

一条路线的“总长度”定义为从访问的第一个城镇到第二个城镇，再到第三个，...，直到最后一个城镇的移动距离之和。

你的任务是计算这 $N!$ 条不同路线的平均长度。

输入格式

输入按以下格式： 第一行包含一个整数 $N$。 接下来 $N$ 行，每行包含两个整数 $x_i, y_i$，表示第 $i$ 个城镇的坐标。

输出格式

输出一个实数，表示所有路线的平均长度。 你的答案将被视为正确，当且仅当其与标准答案的绝对误差或相对误差不超过 $10^{-6}$。

样例

样例输入 #1

3
0 0
1 0
0 1

样例输出 #1

2.2761423749

样例输入 #2

2
-879 981
-866 890

样例输出 #2

91.9238815543

样例输入 #3

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

样例输出 #3

7641.9817824387

提示

样例 1 解释

共有 3 个城镇，因此有 $3! = 6$ 条不同的访问路线。例如，路线 $1 \to 2 \to 3$ 的长度为：

$$\text{dist}(1, 2) + \text{dist}(2, 3) = \sqrt{(0-1)^2 + (0-0)^2} + \sqrt{(1-0)^2 + (0-1)^2} = 1 + \sqrt{2} $$

将所有 6 条路线的长度（分别为 $1+\sqrt{2}, 1+\sqrt{2}, 2, 1+\sqrt{2}, 2, 1+\sqrt{2}$）相加并除以 6，得到的平均长度为 $2.276142\dots$。

数据范围与约定

• $2 \le N \le 8$
• $-1000 \le x_i, y_i \le 1000$
• 对于 $i \neq j$，有 $(x_i, y_i) \neq (x_j, y_j)$
• 所有输入均为整数