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

AT_abc145_c [ABC145C] Average Length

题目描述

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

当你需要依次访问所有城镇各一次时，访问城镇的路径共有 $N!$ 种。从第一个访问的城镇出发，依次经过第二个、第三个，……，直到第 $N$ 个访问的城镇，每次从一个城镇到下一个城镇都按直线移动。每条路径的长度定义为所有相邻城镇之间距离之和。请计算所有 $N!$ 条路径长度的平均值。

输入格式

输入按以下格式从标准输入读入。

$N$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_N$ $y_N$

输出格式

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

样例 1

输入

3
0 0
1 0
0 1

输出

2.2761423749

样例 2

输入

2
-879 981
-866 890

输出

91.9238815543

样例 3

输入

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$
• $(x_i, y_i) \neq (x_j, y_j)$（当 $i \neq j$ 时）
• （21:12 补充）输入中的所有值均为整数。

样例解释 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}$。同理计算其他路径长度，所有路径长度的平均值为 $\frac{(1+\sqrt{2})+(1+\sqrt{2})+(2)+(1+\sqrt{2})+(2)+(1+\sqrt{2})}{6} = 2.276142\ldots$。

样例解释 2

访问城镇的路径有 $1 \to 2$、$2 \to 1$ 共 $2$ 种，这两条路径的长度相同。

由 ChatGPT 4.1 翻译