B. 清点星辰

单测试点时限: 2.0 秒

内存限制: 512 MB

“夜里,
你要抬头仰望满天的星星。
我那颗实在太小了,
我都没法指给你看它在哪儿。”

这样倒也好,我的星星,对你来说就是满天星星中的一颗。

所以,你会爱这满天的星星…所有的星星都会是你的朋友。

即使只能通过狭小的洞口,在楼宇的夹缝中仰望布满星辰的天空,你还是无法割舍对它的期待。

星星数不胜数,但你还是不厌其烦地清点他们。日复一日,终于在今天,你把他们都数清楚了。

于是你又开始找别的事情做了。你开始计算他们两两之间的最近距离。

你仰望星空的洞口是一个 1×1 的正方形,每天,星辰的位置都会发生变化,具体地说,每天都会有 n 个星辰随机地散落在这个正方形内的某个坐标上(每个点横纵坐标满足独立同分布 U(0,1))。

每天的距离都在变化,所以现在你只想知道他们两两之间最近距离的期望是多少。

输入

输入一个整数 n (2≤n≤109) ,表示星辰的数量。

输出

一行一个小数,输出答案。绝对误差在 10−3 内会被视为正确。

样例

input

2

output

0.521405

input

3

output

0.3055302430

提示

对于某连续性随机变量 X,若其取值范围为 Ω,其概率密度函数为 p(x),则其期望定义为 E(X)=∫Ωxp(x)。若要求关于 X 的函数 f(X) 的期望,则 E(f(X))=∫Ωf(x)p(x)。

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

∫10∫10⋯∫102nmin1≤i<j≤n(xi−xj)2+(yi−yj)2−−−−−−−−−−−−−−−−−√ dx1dy1dx2dy2⋯dxndyn

在 n=2 时,该式可以化简为:

 

∫10∫10∫10∫10(x1−x2)2+(y1−y2)2−−−−−−−−−−−−−−−−−−√ dx1dy1dx2dy2

求出该积分的值约为 0.521405。

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

题目复制有变化,原地址:https://acm.ecnu.edu.cn/contest/125/problem/B/#report10 

题意:不说了,都能看懂。

题解:蒙卡洛模拟,说白了就是随机数。看代码:

#include <iostream>
#include <cstdlib>
#include <cmath>
#include <ctime>
using namespace std;
const int MAX = 1e6;
double x[MAX],y[MAX];
int main(){
	 int n,a,b;
	 a=0;
	 b=1;
	 cin >> n;
	 if(n>=888){//n很大后基本就是0,可以跑一下试试,因为开不了1e9的数组而且超时,只能这样,注意:数据误差要求0.001
	 	cout << 0.000000 << endl;
	 	return 0;
	 }
	 double ans=0;
	 int w=1e7/n/n;//保证复杂度为1e7的情况下随机次数最多,就是在不超时情况下,随机次数竟可能多,这样误差就小
	 srand(time(NULL));//以时间种子,防止被卡
	 for (int i = 1; i <= w;i++){
	 	double minn=520;
	 	for (int j = 1; j <= n;j++){
	 		x[j]=((double)rand()/RAND_MAX)*(b-a)+a;//产生a——b之间的随机数
	 		y[j]=((double)rand()/RAND_MAX)*(b-a)+a;
	 		for (int k = 1; k < j;k++) {
				minn=min(minn,sqrt((x[j]-x[k])*(x[j]-x[k])+(y[j]-y[k])*(y[j]-y[k])));
			}
		 }
	 	ans+=minn;//每次情况求和
	 }
	 printf("%.6f\n",ans/w);//求平均数
	return 0;
}