题目描述

小蓝在一个位于平面直角坐标系第一象限的游戏区域玩耍。区域内有 $n$ 颗地雷，第 $i$ 颗地雷位于 $(x_i, y_i)$，其危险范围是以该点为圆心、半径为 $r_i$ 的圆形区域。

小蓝从原点 $(0, 0)$ 出发，他会选择一个介于 $0^\circ$ 到 $90^\circ$（即弧度 $[0, \frac{\pi}{2}]$）之间的方向，然后沿着这个方向做直线运动。如果在运动过程中进入了任何一个地雷的圆形危险区域（包括边界），则游戏失败。如果能一直前进而不触发任何地雷，则游戏成功。

假设小蓝在 $[0, \frac{\pi}{2}]$ 的角度范围内均匀随机地选择一个方向，问他成功通关的概率是多少？

约束：$1 \le n \le 10^5$，$1 \le x_i, y_i \le 10^4$，$r_i < \min(x_i, y_i)$。最后一个条件保证了地雷圆心和其危险区域完全位于第一象限内，且不会包含原点 $(0, 0)$。

样例

输入:
1
2 2 1
输出:
0.540

输入:
2
1 3 1
3 1 1
输出:
0.181

算法 (扫描线 + 角度计算)

$O(n \log n)$

思路分析

1. 问题的几何模型:
   小蓝从原点出发，选择一个角度 $\theta \in [0, \frac{\pi}{2}]$，沿着该方向的射线前进。如果这条射线与任何一个地雷的圆形区域相交，则该方向 $\theta$ 是 “不安全” 的。我们需要计算所有不安全方向所占的角度总长度，然后用总角度范围 $\frac{\pi}{2}$ 减去不安全角度总长度，得到安全角度的总长度，最后除以总角度范围 $\frac{\pi}{2}$ 得到成功的概率。

2. 单个地雷的危险角度范围:
   考虑第 $i$ 颗地雷，圆心 $P_i = (x_i, y_i)$，半径 $r_i$。原点 $O = (0, 0)$。
   从原点 $O$ 出发的射线会与这个圆形区域相交，当且仅当射线的角度 $\theta$ 落在某个特定的区间内。这个区间可以通过几何关系确定：

   • 计算原点 $O$ 到圆心 $P_i$ 的距离 $d_i = \sqrt{x_i^2 + y_i^2}$。
   • 计算向量 $\vec{OP_i}$ 与 $x$ 轴正方向的夹角 $\alpha_i = \mathrm{atan2}(y_i, x_i)$。函数 atan2(y, x) 返回点 $(x, y)$ 相对于原点的极坐标角度（弧度制），范围是 $(-\pi, \pi]$。由于地雷在第一象限，$\alpha_i \in (0, \frac{\pi}{2})$。
   • 从原点 $O$ 向圆 $i$ 可以画两条切线。考虑由原点 $O$、圆心 $P_i$、切点 $T$ 构成的直角三角形 $\triangle OP_iT$。斜边 $OP_i = d_i$，直角边 $P_iT = r_i$。设 $\angle P_iOT = \delta_i$，则有 $\sin(\delta_i) = \frac{r_i}{d_i}$。
   • 因此，半角 $\delta_i = \arcsin\left(\frac{r_i}{d_i}\right)$。由于 $r_i < \min(x_i, y_i) \le \sqrt{x_i^2+y_i^2} = d_i$，所以 $0 < r_i/d_i < 1$，$\arcsin$ 函数总是有定义的，且 $\delta_i \in (0, \frac{\pi}{2})$。
   • 所有与圆盘相交的射线所形成的角度范围是 $[\alpha_i - \delta_i, \alpha_i + \delta_i]$。
   • 我们需要将这个范围与问题限定的角度范围 $[0, \frac{\pi}{2}]$ 取交集。所以，第 $i$ 颗地雷对应的不安全角度区间为：
     $$[s_i, e_i] = [\max(0.0, \alpha_i - \delta_i), \min(\frac{\pi}{2}, \alpha_i + \delta_i)]$$

3. 合并所有危险区间:
   现在我们得到了 $n$ 个可能重叠的不安全角度区间 $[s_1, e_1], [s_2, e_2], \dots, [s_n, e_n]$。我们需要计算这些区间并集的总长度。这是一个标准的一维区间合并问题，可以使用扫描线算法高效解决。

4. 扫描线算法:

   • 事件点: 将每个区间的起始点 $s_i$ 和结束点 $e_i$ 看作是扫描线上的事件点。
   • 事件类型:
     • 起始点 $s_i$ 对应一个“进入”事件，类型记为 $+1$（表示进入了一个危险区间）。
     • 结束点 $e_i$ 对应一个“离开”事件，类型记为 $-1$（表示离开了一个危险区间）。
   • 创建与排序: 为每个有效区间 $[s_i, e_i]$ 创建两个事件 {s_i, +1} 和 {e_i, -1}。将所有 $2n$ 个事件存储在一个列表 ev 中，并按照事件发生的角度 a 升序排序。如果两个事件的角度相同，处理顺序很重要。通常，我们希望在同一位置，先处理完所有离开事件，再处理进入事件，或者反之。代码中的排序规则 a == o.a ? t > o.t : a < o.a 使得类型 -1 (离开) 排在类型 +1 (进入) 之前，这适用于计算区间并集的长度。
   • 扫描过程:
     • 维护一个计数器 active，表示当前扫描线位置（角度）被多少个危险区间覆盖。初始 active = 0。
     • 维护一个变量 unsafe，累积不安全区间的总长度。初始 unsafe = 0。
     • 维护 last 变量，记录上一个事件发生的角度。初始 last = 0。
     • 按顺序遍历排序后的事件列表 ev：
       1. 设当前事件为 {a, t}。
       2. 计算上一个事件点 last 到当前事件点 a 之间的角度差 delta = a - last。
       3. 累加不安全长度: 如果在上一个区间 (last, a) 中，active > 0（即该区间至少被一个危险区间覆盖），则将区间长度 delta 加入到 unsafe 中：unsafe += delta。
       4. 更新状态: 根据当前事件的类型 t 更新计数器：active += t。
       5. 更新位置: 将 last 更新为当前事件的角度 a：last = a。
   • 结果: 遍历完所有事件后，unsafe 就包含了所有危险角度区间并集的总长度。

5. 计算概率:

   • 总的角度范围是 $\frac{\pi}{2}$ (代码中为 PI2)。
   • 安全角度的总长度 safe = PI2 - unsafe。
   • 由于浮点计算可能存在误差，需要确保 unsafe 的值在 $[0, PI2]$ 范围内，所以计算 safe = PI2 - min(PI2, max(0.0, unsafe))。
   • 最终的概率 prob = safe / PI2。
   • 同样，为了确保概率在 $[0, 1]$ 范围内，进行 prob = min(1.0, max(0.0, prob))。
   • 按要求四舍五入保留三位小数输出。

6. 数值精度注意事项:

   • asin 参数范围: asin(x) 函数要求 $x \in [-1, 1]$。计算 r / d 时，由于浮点误差，结果可能略微超出这个范围（例如 1.0000000000000002）。直接调用 asin 会导致 NaN (Not a Number)。代码中使用了 min(1. - 1e-12, max(-1. + 1e-12, r / d))，通过一个极小的容差 1e-12 将参数强制限制在略小于 1 和略大于 -1 的范围内，避免了这个问题。
   • atan2(y, x): 这个函数比 atan(y/x) 更健壮，能正确处理 $x=0$ 的情况，并返回 $(-\pi, \pi]$ 范围内的正确角度。
   • 最终结果钳位: 最后将 unsafe 和 prob 的值钳位（clamp）到合法范围内，是处理浮点误差的良好实践。

时间复杂度

• 对 $n$ 个地雷，计算不安全角度区间需要 $O(n)$ 时间（主要是数学函数调用）。
• 创建 $2n$ 个事件需要 $O(n)$ 时间。
• 对 $2n$ 个事件进行排序需要 $O(n \log n)$ 时间。
• 扫描线过程遍历 $2n$ 个事件，每次处理是 $O(1)$ 的，总共 $O(n)$ 时间。
• 因此，算法的瓶颈在于排序，总时间复杂度为 $O(n \log n)$。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

using namespace std;
using i64 = long long; // 定义 i64 为 long long (本题未使用)

// 定义常量 PI 和 PI 的一半 PI2
constexpr double PI = acos(-1.0), PI2 = PI / 2.0;

// 定义事件结构体
struct E {
    double a; // 事件发生的角度
    int t;    // 事件类型: +1 表示区间开始, -1 表示区间结束
    // 重载小于运算符，用于排序
    // 优先按角度 a 升序排序
    // 如果角度相同，则按类型 t 降序排序 (即 -1 在 +1 之前)
    bool operator<(const E& o) const { return a == o.a ? t > o.t : a < o.a; }
};

int main() {
    // 加速 IO
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; // 地雷数量
    cin >> n;

    vector<E> ev; // 存储所有事件
    // 遍历 n 个地雷
    for (int i = 0; i < n; i++) {
        double x, y, r; // 读入地雷坐标和半径
        cin >> x >> y >> r;
        // 计算原点到圆心的距离 d
        double d = sqrt(x * x + y * y);
        // 计算圆心相对于原点的角度 ca (center angle)
        double ca = atan2(y, x);
        // 计算从原点看圆所张的半角 da (delta angle)
        // 先计算 asin 的参数，并进行精度保护，防止参数超出 [-1, 1]
        double asin_arg = r / d;
        asin_arg = min(1.0 - 1e-12, asin_arg); // 限制上界
        asin_arg = max(-1.0 + 1e-12, asin_arg); // 限制下界
        double da = asin(asin_arg);
        // 计算不安全角度区间的起始点 s 和结束点 e
        // 并确保它们在 [0, PI2] 范围内
        double s = max(0.0, ca - da);
        double e = min(PI2, ca + da);
        // 如果区间有效 (s <= e)
        if (s <= e) {
            // 添加区间开始事件 {角度, 类型+1}
            ev.push_back({s, 1});
            // 添加区间结束事件 {角度, 类型-1}
            ev.push_back({e, -1});
        }
    }

    // 对所有事件进行排序
    sort(ev.begin(), ev.end());

    double unsafe = 0; // 累积的不安全角度总长度
    double last = 0;   // 上一个事件的角度
    int active = 0;    // 当前覆盖扫描线的危险区间数量

    // 执行扫描线算法
    for (auto [a, t] : ev) { // 使用 C++17 结构化绑定遍历事件
        // 计算当前事件与上一个事件之间的角度差 delta = a - last
        // 如果上一个区间 (last, a) 是不安全的 (active > 0)
        // 则将该区间的长度加入 unsafe 总长度
        if (a > last && active > 0) {
            unsafe += a - last;
        }
        // 根据当前事件类型 t 更新活动区间计数
        active += t;
        // 更新上一个事件的角度
        last = a;
    }
    // 循环结束后，unsafe 包含了 [0, last_event_angle] 内的不安全总长度
    // 注意：不需要单独处理 (last, PI2] 区间，因为如果最后一个事件是离开事件，active 会变为 0 或更小；
    // 如果最后一个事件是进入事件，active 会大于 0，但循环已结束，这部分不需要计入。
    // 总之，扫描到最后一个事件点即可。

    // 计算安全角度总长度，钳位 unsafe 到 [0, PI2]
    double safe = PI2 - min(PI2, max(0.0, unsafe));
    // 计算概率
    double prob = safe / PI2;
    // 输出结果，保留三位小数，并钳位 prob 到 [0, 1]
    cout << fixed << setprecision(3) << min(1.0, max(0.0, prob)) << "\n";

    return 0; // 程序正常结束
}