蒙特卡洛

GitHub跳转原题关系图Canvas 关系图返回列表

统计给定坐标中满足 x^2+y^2<=a^2 的点数，再按 4m/n 计算圆周率估计值。

OJ: shumeng

题目 ID: CSP202509A

难度:入门

标签:模拟数学浮点数

日期: 2026-07-31 16:21

目录

  1. 形式化题目
  2. 思路
    1. 边界处理
    2. 输出格式
  3. 代码
  4. 复杂度
  5. 总结

形式化题目

在边长为 2a2a 的正方形中随机生成 nn 个点。统计落在以原点为圆心、半径为 aa 的圆内（含边界）的点数 mm，输出 4mn\dfrac{4m}{n}。

思路

点 (x,y)(x,y) 在圆内当且仅当 x2+y2≤a2x^2 + y^2 \le a^2，逐点判断并计数即可。

边界处理

圆内"含边界"，判断用 ≤\le。由于浮点计算可能有微小误差，比较时在 a2a^2 上加上一个小量（如 1e-12），确保恰好落在圆上的点被计入。

输出格式

题目按绝对误差小于 0.00010.0001 评分，保留 6 位小数输出最稳妥。

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:59
 */
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    double a;
    cin >> n >> a;

    // 统计落在圆内(含边界)的点的个数
    int inside = 0;
    for (int i = 0; i < n; i++) {
        double x, y;
        cin >> x >> y;
        // 半径 a 的圆内条件：x^2 + y^2 <= a^2，加小量吸收浮点误差
        if (x * x + y * y <= a * a + 1e-12) inside++;
    }

    // 蒙特卡洛估计：pi ≈ 4 * m / n，保留 6 位小数
    cout << fixed << setprecision(6) << 4.0 * inside / n << '\n';
    return 0;
}

复杂度

需要扫描全部 nn 个点，时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。

总结

本题是蒙特卡洛模拟的简化版，核心就是圆的判定式 x2+y2≤a2x^2+y^2 \le a^2。注意边界点计入圆内，以及用 double 计算时的小量容差。