题解：P12144 [蓝桥杯 2025 省 A] 地雷阵
Shadow_Soldier
·
·
题解
前言
本文中所有三角函数与角度均采用弧度制（如有特殊情况，会注明）。
感谢大佬 @cserzy 的提醒，我的题解中有一个错误（O 一定在 \odot P_i 外），现已改正（2025 年 4 月 15 日）。
感谢大佬 @Hanwenhu 的提醒，我的题解中有一个错误（\angle A_{i,1}OP_i 的计算方法应使用 \arcsin，而不是 \arccos），现已改正（2025 年 5 月 5 日）。
我自己发现了我的题解中的一个错误（OP_i = \sqrt{{x_i}^2 + {y_i}^2}，而不是 \sqrt{x^2+y^2}），现已改正（2025 年 5 月 5 日）。
感谢大佬兼紫名管理员 @chen_zhe 的提醒，我的题解中图片爆了，现已修正（2025 年 10 月 16 日）
题意简述
已知一平面直角坐标系 xOy 中的第一象限上有 n(n \in \N^*,n \le 10^5) 个点 P_1,P_2,\cdots,P_n。其中，若有正整数 i，满足 1 \le i \le n，则 P_i(x_i,y_i)(x_i,y_i \in \N^*)。给出 n 个正整数 r_1,r_2,\cdots,r_n，以 P_i 为圆心，半径长为 r_i，分别作 \odot P_1,\odot P_2,\cdots,\odot P_n。问：若从原点 O 出发，在 [0,\frac{\pi}{2}]（即 0^{\circ}（角度制，朝 x 轴方向）至 {90}^{\circ}（角度制，朝 y 轴方向））中随机选择一个方向，作一条直线不与任何一个圆相交的概率是多少（保留三位小数）？
题目链接
正解思路
第一步
对于每个 P_i，连接 OP_i，设 OP_i = d。
作 P_iM \perp x \text{ 轴}，则 OM = x_i，P_iM = y_i。由勾股定理，Rt \triangle OMP_i 中，OP_i = \sqrt{OM^2 + P_iM^2} = \sqrt{{x_i}^2 + {y_i}^2}。所以，d = \sqrt{{x_i}^2 + {y_i}^2}。
因为 x_i,y_i > 0，所以 d \ge \min(x_i, y_i)。又因为 r_i < \min(x_i, y_i)，所以 d > r。
所以，O 在 \odot P_i 外。
如图，过 O 作 \odot P_i 的切线 OA_{i,1} 与 OA_{i,2}，连接 A_{i,1}P 与 A_{i,2}P。
下面对图中的情况进行讨论。
注意到此时 \odot P_i 挡住的是一部分的直线，所以可以理解为挡住了 [\angle A_{i,1}OM_i,\angle A_{i,2}OM_i] 的方向。
因为 P_iA_{i,1} \perp OA_{i,1} 且 P_iA_{i,2} \perp OA_{i,2}，所以 \triangle OA_{i,1}P_i 与 \triangle OA_{i,2}P_i 都是直角三角形。因为 A_{i,1}P_i = A_{i,2}P_i 且 OP_i = OP_i，所以 \triangle OA_{i,1}P_i \cong \triangle OA_{i,2}P_i。进而 \angle A_{i,1}OP_i = \angle A_{i,2}OP_i。
注意到，\angle P_iOM_i = \arctan(\frac{P_iM_i}{OM_i}) = \arctan(\frac{y_i}{x_i})，\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}})。又因为 \angle A_{i,1}OP_i = \angle A_{i,2}OP_i，所以 \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}})，\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(\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,\frac{\pi}{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})]。
第二步
那么，总共不可行的区间加在一起有多长呢（不能重复）？这也很简单了。只要把这些区间合并一下就好了，我们只要记录最后的区间并在计算过程中统计答案（答案初值为 0）。
按照区间的最低限度从小往大排序，然后正序扫描一遍。
如果目前没有一个区间，则就直接把这个区间赋值为现在的区间。否则，分两种情况讨论：
- 最后的区间的最大限度大于等于这个区间的最小限度：最后的区间的最大限度值为它与这个区间的最大限度的最大值。
- 否则：把答案加上最后的区间的最大限度与最小限度的差，然后把最后的区间赋值为这个区间。
最后，把答案加上最后的区间的最大限度与最小限度的差，并根据这个值推导出最终的概率（\text{概率} = \text{1} - \frac{\text{答案}}{\frac{\pi}{2}}）。
代码
在放代码之前，先提醒一下：
- 使用
double 作为变量类型
- 提前求出 \frac{\pi}{2}。
#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;
}
提交记录
链接：我的提交记录;