3658. 清点星辰

输入格式

输入一个整数 $n$ ($2 \le n \le 10^9$) ，表示星辰的数量。

输出格式

一行一个小数，输出答案。绝对误差在 $10^{-3}$ 内会被视为正确。

2

0.521405

3

0.3055302430

提示

对于某连续性随机变量 $X$，若其取值范围为 $\Omega$，其概率密度函数为 $p(x)$，则其期望定义为 $E(X) = \int_{\Omega} x p(x)$。若要求关于 $X$ 的函数 $f(X)$ 的期望，则 $E(f(X)) = \int_{\Omega} f(x) p(x)$。

该式子可以在多变量上进行推广，如果有两个随机变量 $X$, $Y$，则关于 $X,Y$ 的函数 $f(X, Y)$ 的期望可以定义为 $E(f(X,Y)) = \int_{\Omega} f(x,y) p(x,y)$，其中 $p(x,y)$ 是 $x,y$ 的联合概率密度函数。在 $X$ 和 $Y$ 独立时，$p(x,y) = p(x)p(y)$

在本题中，所有变量的概率密度函数都是 $p(x)=1,0<x<1$。故所求式可以写为：

$\overbrace{ \int_0^1 \int_0^1 \cdots \int_0^1 }^{ 2n } \min_{1\le i < j \le n} \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2} \text{ dx}_1 \text{dy}_1 \text{dx}_2 \text{dy}_2 \cdots \text{dx}_n \text{dy}_n$

在 $n=2$ 时，该式可以化简为：

$$\int_0^1 \int_0^1 \int_0^1 \int_0^1 \sqrt{(x_1-x_2)^2 + (y_1 - y_2)^2} \text{ dx}_1 \text{dy}_1 \text{dx}_2 \text{dy}_2$$

求出该积分的值约为 $0.521405$。

在 $n>2​$ 的情形下，由于式子中有 $\min$，积分式十分复杂，很有可能没有解析解。在定积分不可行的情况下，可以采用数值逼近的方法近似计算给定的定积分值，这种方法称为数值积分。借助于电子计算设备，数值积分可以快速而有效地计算复杂的积分。数值积分常用的方法包括矩形法、辛普森积分法等。更多有关数值积分的数学原理和算法介绍，读者可以自行阅读维基百科。