专栏文章

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

MMasterArcherSkeleton
P12144题解参与者 4已保存评论 7

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
7 条
当前快照
1 份
快照标识符
@miplzo0x
此快照首次捕获于
2025/12/03 14:11
3 个月前
此快照最后确认于
2025/12/03 14:11
3 个月前
查看原文

前言

本文中所有三角函数与角度均采用弧度制（如有特殊情况，会注明）。
感谢大佬 @cserzy 的提醒，我的题解中有一个错误（OO 一定在 ⊙Pi\odot P_i 外），现已改正（2025 年 4 月 15 日）。
感谢大佬 @Hanwenhu 的提醒，我的题解中有一个错误（∠Ai,1OPi\angle A_{i,1}OP_i 的计算方法应使用 arcsin⁡\arcsin，而不是 arccos⁡\arccos），现已改正（2025 年 5 月 5 日）。
我自己发现了我的题解中的一个错误（OPi=xi2+yi2OP_i = \sqrt{{x_i}^2 + {y_i}^2}，而不是 x2+y2\sqrt{x^2+y^2}），现已改正（2025 年 5 月 5 日）。
感谢大佬兼紫名管理员 @chen_zhe 的提醒，我的题解中图片爆了，现已修正（2025 年 10 月 16 日）

题意简述

已知一平面直角坐标系 xOyxOy 中的第一象限上有 n(n∈N∗,n≤105)n(n \in \N^*,n \le 10^5) 个点 P1,P2,⋯ ,PnP_1,P_2,\cdots,P_n。其中，若有正整数 ii，满足 1≤i≤n1 \le i \le n，则 Pi(xi,yi)(xi,yi∈N∗)P_i(x_i,y_i)(x_i,y_i \in \N^*)。给出 nn 个正整数 r1,r2,⋯ ,rnr_1,r_2,\cdots,r_n，以 PiP_i 为圆心，半径长为 rir_i，分别作 ⊙P1,⊙P2,⋯ ,⊙Pn\odot P_1,\odot P_2,\cdots,\odot P_n。问：若从原点 OO 出发，在 [0,π2][0,\frac{\pi}{2}]（即 0∘0^{\circ}（角度制，朝 xx 轴方向）至 90∘{90}^{\circ}（角度制，朝 yy 轴方向））中随机选择一个方向，作一条直线不与任何一个圆相交的概率是多少（保留三位小数）？
题目链接

正解思路

第一步

对于每个 PiP_i，连接 OPiOP_i，设 OPi=dOP_i = d。
作 PiM⊥x 轴P_iM \perp x \text{ 轴}，则 OM=xiOM = x_i，PiM=yiP_iM = y_i。由勾股定理，Rt△OMPiRt \triangle OMP_i 中，OPi=OM2+PiM2=xi2+yi2OP_i = \sqrt{OM^2 + P_iM^2} = \sqrt{{x_i}^2 + {y_i}^2}。所以，d=xi2+yi2d = \sqrt{{x_i}^2 + {y_i}^2}。
因为 xi,yi>0x_i,y_i > 0，所以 d≥min⁡(xi,yi)d \ge \min(x_i, y_i)。又因为 ri<min⁡(xi,yi)r_i < \min(x_i, y_i)，所以 d>rd > r。
所以，OO 在 ⊙Pi\odot P_i 外。
图
如图，过 OO 作 ⊙Pi\odot P_i 的切线 OAi,1OA_{i,1} 与 OAi,2OA_{i,2}，连接 Ai,1PA_{i,1}P 与 Ai,2PA_{i,2}P。
下面对图中的情况进行讨论。 注意到此时 ⊙Pi\odot P_i 挡住的是一部分的直线，所以可以理解为挡住了 [∠Ai,1OMi,∠Ai,2OMi][\angle A_{i,1}OM_i,\angle A_{i,2}OM_i] 的方向。
因为 PiAi,1⊥OAi,1P_iA_{i,1} \perp OA_{i,1} 且 PiAi,2⊥OAi,2P_iA_{i,2} \perp OA_{i,2}，所以 △OAi,1Pi\triangle OA_{i,1}P_i 与 △OAi,2Pi\triangle OA_{i,2}P_i 都是直角三角形。因为 Ai,1Pi=Ai,2PiA_{i,1}P_i = A_{i,2}P_i 且 OPi=OPiOP_i = OP_i，所以 △OAi,1Pi≅△OAi,2Pi\triangle OA_{i,1}P_i \cong \triangle OA_{i,2}P_i。进而 ∠Ai,1OPi=∠Ai,2OPi\angle A_{i,1}OP_i = \angle A_{i,2}OP_i。
注意到，∠PiOMi=arctan⁡(PiMiOMi)=arctan⁡(yixi)\angle P_iOM_i = \arctan(\frac{P_iM_i}{OM_i}) = \arctan(\frac{y_i}{x_i})，∠Ai,1OPi=arcsin⁡(Ai,1PiOPi)=arcsin⁡(rid)=arcsin⁡(rixi2+yi2)\angle A_{i,1}OP_i = \arcsin(\frac{A_{i,1}P_i}{OP_i}) = \arcsin(\frac{r_i}{d}) = \arcsin(\frac{r_i}{\sqrt{{x_i}^2 + {y_i}^2}})。又因为 ∠Ai,1OPi=∠Ai,2OPi\angle A_{i,1}OP_i = \angle A_{i,2}OP_i，所以 ∠Ai,1OMi=∠PiOMi−∠Ai,1OPi=arctan⁡(yixi)−arcsin⁡(rixi2+yi2)\angle A_{i,1}OM_i = \angle P_iOM_i - \angle A_{i,1}OP_i = \arctan(\frac{y_i}{x_i}) - \arcsin(\frac{r_i}{\sqrt{{x_i}^2 + {y_i}^2}})，∠Ai,2OMi=∠PiOMi+∠Ai,2OPi=∠PiOMi+∠Ai,1OPi=arctan⁡(yixi)+arcsin⁡(rixi2+yi2)\angle A_{i,2}OM_i = \angle P_iOM_i + \angle A_{i,2}OP_i = \angle P_iOM_i + \angle A_{i,1}OP_i = \arctan(\frac{y_i}{x_i}) + \arcsin(\frac{r_i}{\sqrt{{x_i}^2 + {y_i}^2}})。
所以，此时挡住方向的范围就是 [arctan⁡(yixi)−arcsin⁡(rixi2+yi2),arctan⁡(yixi)+arcsin⁡(rixi2+yi2)][\arctan(\frac{y_i}{x_i}) - \arcsin(\frac{r_i}{\sqrt{{x_i}^2 + {y_i}^2}}), \arctan(\frac{y_i}{x_i}) + \arcsin(\frac{r_i}{\sqrt{{x_i}^2 + {y_i}^2}})]。
但是，其实挡住方向的范围可能有一些并不含在 [0,π2][0,\frac{\pi}{2}] 中，所以正确的答案应该是：[max⁡(arctan⁡(yixi)−arcsin⁡(rixi2+yi2),0),min⁡(arctan⁡(yixi)+arcsin⁡(rixi2+yi2),π2)][\max(\arctan(\frac{y_i}{x_i}) - \arcsin(\frac{r_i}{\sqrt{{x_i}^2 + {y_i}^2}}), 0), \min(\arctan(\frac{y_i}{x_i}) + \arcsin(\frac{r_i}{\sqrt{{x_i}^2 + {y_i}^2}}), \frac{\pi}{2})]。

第二步

那么，总共不可行的区间加在一起有多长呢（不能重复）？这也很简单了。只要把这些区间合并一下就好了，我们只要记录最后的区间并在计算过程中统计答案（答案初值为 00）。
按照区间的最低限度从小往大排序，然后正序扫描一遍。
如果目前没有一个区间，则就直接把这个区间赋值为现在的区间。否则，分两种情况讨论：
  • 最后的区间的最大限度大于等于这个区间的最小限度：最后的区间的最大限度值为它与这个区间的最大限度的最大值。
  • 否则：把答案加上最后的区间的最大限度与最小限度的差，然后把最后的区间赋值为这个区间。
最后，把答案加上最后的区间的最大限度与最小限度的差，并根据这个值推导出最终的概率（概率=1−答案π2\text{概率} = \text{1} - \frac{\text{答案}}{\frac{\pi}{2}}）。

代码

在放代码之前，先提醒一下：
  1. 使用 double 作为变量类型
  2. 提前求出 π2\frac{\pi}{2}。
CPP
#include <bits/stdc++.h>
using namespace std;
int n;
const double pi_2 = asin(1);
const double eps = 1e-8;
double x, y, r, t1, t2, d, ans;
pair<double, double> a[100010], lst;
double Max(double u, double v) {
    return (u > v) ? u : v;
}
double Min(double u, double v) {
    return (u < v) ? u : v;
}
double Abs(double u) {
    return (u < 0) ? (0 - u) : u;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    cout << fixed << setprecision(3);
    for(int i = 1; i <= n; i ++) {
        cin >> x >> y >> r;
        d = sqrt(x * x + y * y);
        t1 = atan(y / x);
        t2 = asin(r / d);
        a[i].first = Max(t1 - t2, 0);
        a[i].second = Min(t1 + t2, pi_2);
    }
    sort(a + 1, a + n + 1);
    lst = make_pair(-1, -1);
    for(int i = 1; i <= n; i ++) {
        if(lst.second >= a[i].first) lst.second = Max(lst.second, a[i].second);
        else {
            ans += (lst.second - lst.first);
            lst = a[i];
        }
    }
    ans += (lst.second - lst.first);
    cout << 1 - ans / pi_2;
    return 0;
}

提交记录

链接：我的提交记录;

评论

共 7 条评论，欢迎与作者交流。

正在加载评论...