EOJ Monthly 2018.12

输入格式

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

输出格式

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

2

0.521405

3

0.3055302430

提示

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

该式子可以在多变量上进行推广，如果有两个随机变量 $X$, $Y$，则关于 $X,Y$ 的函数 $f(X,Y)$ 的期望可以定义为 $E(f(X,Y))={\int }_{\mathrm{\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$。故所求式可以写为：

$\stackrel{2n}{\overbrace{{\int }_0^1{\int }_0^1\cdots {\int }_0^1}}\underset{1\le i<j\le n}{min}\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$，积分式十分复杂，很有可能没有解析解。在定积分不可行的情况下，可以采用数值逼近的方法近似计算给定的定积分值，这种方法称为数值积分。借助于电子计算设备，数值积分可以快速而有效地计算复杂的积分。数值积分常用的方法包括矩形法、辛普森积分法等。更多有关数值积分的数学原理和算法介绍，读者可以自行阅读维基百科。