EOJ2658 清点星辰
题目链接
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; }