题解：P12144 [蓝桥杯 2025 省 A] 地雷阵

· · 题解

P12144 [蓝桥杯 2025 省 A] 地雷阵题解

倒数第二题的位置，简单解析几何 + 区间覆盖问题。死去的解析几何突然攻击我。

核心过程

（一）求过原点且与圆相切的直线斜率

假设一条过原点的直线 y=kx 与圆相切，也就是这条直线 kx-y=0 距离圆心 (x_0,y_0) 的距离为半径 r，可以得到：

\frac{\left\lvert kx_0-y_0 \right\rvert }{\sqrt{k^2+1} } =r

两边同时平方：

\frac{k^2x_0^2-2x_0y_0k+y_0^2}{k^2+1} =r^2 (x_0^2-r^2)k^2-2x_0y_0k+(y_0^2-r^2)=0

求根公式表示出 k：

k=\frac{2x_0y_0\pm \sqrt{4x_0^2y_0^2-4(x_0^2-r^2)(y_0^2-r^2)}}{2x_0^2-2r^2}

化简后得到 k：

\boxed{k=\frac{x_0y_0\pm \sqrt{x_0^2r^2+y_0^2r^2-r^4}}{x_0^2-r^2}}

或者使用圆的方程和判别式来求解：

(x-x_0)^2+(y-y_0)^2=r^2

将 y=kx 代入：

(x-x_0)^2+(kx-y_0)^2=r^2

展开：

x^2 - 2x_0x + x_0^2 + k^2x^2 - 2kxy_0 + y_0^2 = r^2 (1 + k^2)x^2 - 2(x_0 + ky_0)x + (x_0^2 + y_0^2 - r^2) = 0

由于相切（一个交点，判别式为零）：

\Delta =[-2(x_0 + ky_0)]^2 - 4(1 + k^2)(x_0^2 + y_0^2 - r^2) = 0

得到关于 k 的方程：

(x_0 + ky_0)^2 - (1 + k^2)(x_0^2 + y_0^2 - r^2) = 0

化简后也可以得到 k：

\boxed{k=\frac{x_0y_0\pm \sqrt{x_0^2r^2+y_0^2r^2-r^4}}{x_0^2-r^2}}

代码实现：

double k1 = (x*y - sqrt(x*x*r*r + y*y*r*r - r*r*r*r)) / (x*x - r*r);  //* 斜率较小的切线
double k2 = (x*y + sqrt(x*x*r*r + y*y*r*r - r*r*r*r)) / (x*x - r*r);  //* 斜率较大的切线

（二）利用反函数将斜率转换为弧度

对于 \tan(\theta) = k 可以利用反函数求出其对应弧度 \theta =\arctan(k)。

在结构体中：

例：圆心为 (3,4) 半径为 1 的圆所覆盖的弧度为 [\theta_x,\theta_y]。

将这个弧度范围区间添加进 vec 中。

代码实现：

Node tmp;
tmp.x = atan(k1);
tmp.y = atan(k2);
vec.push_back(tmp);

或者直接：

vec.push_back({atan(k1), atan(k2)});

（三）区间覆盖问题

将 vec 排序后，维护 \text{tl} 和 \text{tr} 使其成为当前区间的左右端点。

如果新的区间比当前区间的右端点还要大，说明是下一个区间，用 \text{ans} 累加当前区间。其中，\text{ans} 是所有圆能覆盖弧度范围区间的和。

之后对左右端点进行初始化。

不要忘记遍历完 vec 后还要累加最后的那个区间！

代码实现：

double tl = 0, tr = 0;
double ans = 0;
for (int i = 0; i < vec.size(); i++) {
    if (vec[i].x > tr) {
        ans += tr - tl;
        tl = vec[i].x;
        tr = vec[i].y;
    } else {
        tr = max(tr, vec[i].y);
    } 
}
ans += tr - tl;  //! 不要忘记

（四）输出答案

由于 \text{ans} 记录的是所有圆能覆盖弧度范围区间的和，答案自然是用 1 减去失败的概率，注意保留三位小数。

代码实现：

cout << fixed << setprecision(3) << 1 - ans / (pi / 2) << endl;

完整代码

#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);  //! 加强精度
struct Node {
    double x, y;
};
vector<Node> vec;
bool cmp(Node a, Node b) {
    return (a.x != b.x ? a.x < b.x : a.y < b.y);
}
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        double x, y, r;
        cin >> x >> y >> r;
        double k1 = (x*y - sqrt(x*x*r*r + y*y*r*r - r*r*r*r)) / (x*x - r*r);  //* 斜率较小的切线
        double k2 = (x*y + sqrt(x*x*r*r + y*y*r*r - r*r*r*r)) / (x*x - r*r);  //* 斜率较大的切线
        Node tmp;
        tmp.x = atan(k1);
        tmp.y = atan(k2);
        vec.push_back(tmp);
        // vec.push_back({atan(k1), atan(k2)});
    }

    sort(vec.begin(), vec.end(), cmp);

    double tl = 0, tr = 0;
    double ans = 0;
    for (int i = 0; i < vec.size(); i++) {
        if (vec[i].x > tr) {
            ans += tr - tl;
            tl = vec[i].x;
            tr = vec[i].y;
        } else {
            tr = max(tr, vec[i].y);
        } 
    }
    ans += tr - tl;  //! 不要忘记
    cout << fixed << setprecision(3) << 1 - ans / (pi / 2) << endl; 
    return 0; 
}

一些疑惑

考试的时候读了很多遍题目，数据范围中明确标注是 r_i<\min(x_i,y_i)，便没有写针对与 x 轴相切和与 y 轴相切（斜率为 0 或斜率不存在）的特判。但样例 2 中的两个圆都是不满足数据范围的。

注意事项

目前蓝桥杯只能支持到「极为先进」的 C++11 标准，如果以蓝桥杯为导向练习题目，请避免使用高级语法。

2025/04/17 更新：使用 pi = acos(-1) 加强 \pi 的精度。

2025/12/05 更新：修改部分笔误。