题目链接

https://acm.ecnu.edu.cn/problem/3658/

题目大意

一个 $1 \times 1$ 的正方形中放入 $n$ 个点，问你这 $n$ 个点中最近的两个点的期望距离是多少

题目分析

虽然题目下方的提示中提示了怎么积分，但是好像并没有什么用。考虑题目要求的精度为 $10 ^ {-3}$ 并不是很高，可以使用随机算法。在正方形中随机撒入 $n$ 个点并计算距离，多次撒点后取平均值即可。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <ctime>

using namespace std;

const int maxn = 1e4 + 5;

int n, t;

double ans = 0;

double x[maxn];
double y[maxn];

double sqr(double a){
    return a * a;
}

double getdis(int a, int b){
    return sqrt(sqr(x[a] - x[b]) + sqr(y[a] - y[b]));
}

int main(){
    int i, j, k;
    double minx;
    
    srand(time(0));
    
    cin >> n;
    
    t = 1e7 / n / n;
    
    if(t == 0){
        cout << 0 << endl;
        return 0;
    }
    
    for(k=1;k<=t;k++){
        for(i=1;i<=n;i++){
            x[i] = (double)(1ll * rand() * rand() % 1000000) / 1e6;
            y[i] = (double)(1ll * rand() * rand() % 1000000) / 1e6;
        }
        
        minx = 1e5;
        
        for(i=1;i<=n;i++){
            for(j=i+1;j<=n;j++){
                minx = min(minx, getdis(i, j));
            }
        }
        ans += minx;
    }
    
    printf("%.14f", ans / (double)t);
    
    return 0;
}