A7563. [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!$ 种。从第一个访问的城镇出发，依次经过第二个、第三个，……，直到第 $N$ 个访问的城镇，每次从一个城镇到下一个城镇都按直线移动。每条路径的长度定义为所有相邻城镇之间距离之和。请计算所有 $N!$ 条路径长度的平均值。
输入格式
输入按以下格式从标准输入读入。
> $N$
> $x_1$ $y_1$
> $x_2$ $y_2$
> $\vdots$
> $x_N$ $y_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
输出 #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
说明/提示
## 约束条件
- $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$ 种，这两条路径的长度相同。
- $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$ 种，这两条路径的长度相同。