80 人解决，100 人已尝试。
150 份提交通过，共有 657 份提交。
3.8 EMB 奖励。
3658. 清点星辰
单点时限: 2.0 sec
内存限制: 512 MB
“夜里，
你要抬头仰望满天的星星。
我那颗实在太小了，
我都没法指给你看它在哪儿。”
这样倒也好，我的星星，对你来说就是满天星星中的一颗。
所以，你会爱这满天的星星…所有的星星都会是你的朋友。
即使只能通过狭小的洞口，在楼宇的夹缝中仰望布满星辰的天空，你还是无法割舍对它的期待。
星星数不胜数，但你还是不厌其烦地清点他们。日复一日，终于在今天，你把他们都数清楚了。
于是你又开始找别的事情做了。你开始计算他们两两之间的最近距离。
你仰望星空的洞口是一个 $1 \times 1$ 的正方形，每天，星辰的位置都会发生变化，具体地说，每天都会有 $n$ 个星辰随机地散落在这个正方形内的某个坐标上（每个点横纵坐标满足独立同分布 $U(0,1)$）。
每天的距离都在变化，所以现在你只想知道他们两两之间最近距离的期望是多少。
输入格式
输入一个整数 $n$ ($2 \le n \le 10^9$) ，表示星辰的数量。
输出格式
一行一个小数，输出答案。绝对误差在 $10^{-3}$ 内会被视为正确。
样例
Input
2
Output
0.521405
Input
3
Output
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$，积分式十分复杂，很有可能没有解析解。在定积分不可行的情况下，可以采用数值逼近的方法近似计算给定的定积分值，这种方法称为数值积分。借助于电子计算设备，数值积分可以快速而有效地计算复杂的积分。数值积分常用的方法包括矩形法、辛普森积分法等。更多有关数值积分的数学原理和算法介绍，读者可以自行阅读维基百科。
题目标签