当前位置：首页 > 蓝桥杯 > 2025蓝桥杯省赛A组地雷阵题解：几何转化与区间合并算法详解

2025蓝桥杯省赛A组地雷阵题解：几何转化与区间合并算法详解

8小时前

一、题目解读

2025年蓝桥杯省赛A组地雷阵题目（洛谷12144）要求计算在平面直角坐标系第一象限中，给定n个地雷的位置坐标和触发半径，从原点出发随机选择一个方向行走，不触发地雷的通关概率。题目将游戏问题转化为几何计算：需统计危险角度区间，并通过概率公式求解。

二、解题思路

核心思想是几何转化+区间合并：

1. 危险角度计算：每个地雷对应一个危险角度区间，通过计算地雷圆心到原点连线与x轴的夹角α及切线夹角θ，得到区间[α-θ, α+θ]。

2. 区间合并：合并重叠区间，减少危险角度总量，避免重复计算。

3. 概率计算：用总危险角度占[0, π/2]的比例，反推安全概率。

特殊处理：若原点在地雷范围内，直接输出0，避免后续计算。

三、解题步骤

1. 输入与预处理：读取n个地雷的(x,y,r)，判断原点是否在地雷内。

2. 计算单个危险区间：

计算地雷到原点距离d与夹角α。

若d≤r，原点触发，结束；否则计算切线夹角θ，形成区间[L, R]。

3. 合并区间：

按左端点排序，遍历合并重叠区间（如新区间与当前区间右端重叠，扩展右端）。

4. 计算总危险角度：累加合并后区间的长度。

5. 输出概率：1 - (危险角度 / π/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;
    }
    
    // 输出安全概率
    cout << fixed << setprecision(3) << 1 - (danger / (PI / 2));
}

注释说明：

● Interval结构定义角度区间，用于存储危险范围。

● atan2(y, x)计算带象限的反正切，确保角度正确。

● 区间合并逻辑通过贪心策略，维护左端点递增的区间列表。