← 返回题目列表

AtCoder · abc145_c

C. 平均长度

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

有 N 坐标平面中的城镇。镇 i 位于坐标 (x_i, y_i)。城镇之间的距离 i 和镇 j is \sqrt{\left(x_i-x_j\right)^2+\left(y_i-y_j\right)^2}.

有 N! 访问所有这些城镇一次的可能路径。设路径的长度为我们从路径中的第一个城镇出发,访问第二个、第三个、 \dots,城镇,并到达最后一个城镇(假设我们从一个城镇直线行驶到另一个城镇)。计算这些的平均长度 N! 路径。

约束

  • 2 \leq N \leq 8
  • -1000 \leq x_i \leq 1000
  • -1000 \leq y_i \leq 1000
  • \left(x_i, y_i\right) \neq \left(x_j, y_j\right) (如果 i \neq j)
  • (日本标准时间 21:12 添加)输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
x_1 y_1
:
x_N y_N

输出

打印路径的平均长度。 当你的输出与法官输出的绝对差值最多为时,你的输出将被判定为正确 10^{-6}.


示例输入 1

3
0 0
1 0
0 1

示例输出 1

2.2761423749

参观城镇有六种路径: 1 → 2 → 3, 1 → 3 → 2, 2 → 1 → 3, 2 → 3 → 1, 3 → 1 → 2,和 3 → 2 → 1.

路径的长度 1 → 2 → 3 is \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.9238815543

游览城镇有两条路径: 1 → 2 和 2 → 1。这些路径具有相同的长度。


示例输入 3

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

示例输出 3

7641.9817824387