2025年蓝桥杯省赛A组地雷阵（洛谷P12144）题解：数学建模与算法实现详解

22小时前比赛题解23

一、问题重述

小蓝在平面直角坐标系的第一象限玩逃生游戏。原点(0,0)是起点，第一象限内有n个圆形地雷。小蓝随机选择一个方向(0°到90°之间)直线前进，求不碰到任何地雷的概率。

二、核心思路

‌几何转换‌：将地雷的圆形危险区域转换为角度区间
‌区间合并‌：合并重叠的危险角度区间
‌概率计算‌：安全角度范围占总角度的比例

三、详细解析

1. 单个地雷的危险角度计算

对于每个地雷，我们需要计算从原点出发的直线何时会进入该地雷的圆形区域。这可以通过计算切线与x轴的夹角来实现。

计算地雷中心到原点的距离：d = sqrt(x² + y²)
计算切线与中心线的夹角：θ = asin(r/d)
计算地雷中心与x轴的夹角：α = atan2(y, x)
危险角度区间为：[α-θ, α+θ]

2. 角度区间处理

由于题目限制在[0, π/2]范围内，我们需要：

丢弃完全在范围外的区间
截断部分在范围内的区间

3. 区间合并算法

为了准确计算总危险范围，我们需要合并重叠或相邻的区间：

按区间起点排序
遍历区间，合并重叠部分

4. 概率计算

总安全角度 = π/2 - 总危险角度
概率 = 安全角度 / (π/2)

四、实现代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespACe std;

const double PI = acos(-1.0);

// 表示一个角度区间
struct Interval {
    double l, r;
    Interval(double _l = 0, double _r = 0) : l(_l), r(_r) {}
    bool operator<(const Interval& other) const {
        return l < other.l;
    }
};

int main() {
    int n;
    cin >> n;
    vector<Interval> intervals;
    
    for (int i = 0; i < n; ++i) {
        double x, y, r;
        cin >> x >> y >> r;
        
        // 计算地雷中心到原点的距离
        double d = sqrt(x * x + y * y);
        if (d <= r) {
            // 如果原点在地雷范围内，所有方向都会触发地雷
            cout << "0.000" << endl;
            return 0;
        }
        
        // 计算切线与x轴的夹角
        double theta = asin(r / d);
        // 计算地雷中心与x轴的夹角
        double alpha = atan2(y, x);
        
        // 计算危险角度区间
        double L = alpha - theta;
        double R = alpha + theta;
        
        // 确保角度在[0, PI/2]范围内
        if (R < 0) continue; // 完全在左边，不影响
        if (L > PI/2) continue; // 完全在右边，不影响
        
        L = max(L, 0.0);
        R = min(R, PI/2);
        
        if (L < R) {
            intervals.emplace_back(L, R);
        }
    }
    
    // 合并重叠的区间
    if (!intervals.empty()) {
        sort(intervals.begin(), intervals.end());
        vector<Interval> merged;
        merged.push_back(intervals[0]);
        
        for (int i = 1; i < intervals.size(); ++i) {
            if (intervals[i].l <= merged.back().r) {
                merged.back().r = max(merged.back().r, intervals[i].r);
            } else {
                merged.push_back(intervals[i]);
            }
        }
        
        intervals = merged;
    }
    
    // 计算总危险角度范围
    double danger = 0;
    for (const auto& interval : intervals) {
        danger += interval.r - interval.l;
    }
    
    // 计算安全角度范围
    double safe = PI/2 - danger;
    double probability = safe / (PI/2);
    
    // 输出结果，保留三位小数
    cout << fixed << setprecision(3) << probability << endl;
    
    return 0;
}