[NCT058A]签到题 - 题解

标签与难度

标签: 二分查找, 计算几何, 排序, 预处理, 坐标难度: 1300

题目大意喵~

你好呀，未来的算法大师！本喵今天带来的这道题，听起来就像是在星空下画圈圈一样浪漫呢，喵~

题目是这样说的：在一个平面直角坐标系里，有 $n$ 个圆，它们的圆心都在原点 $O(0, 0)$ ，只是半径各不相同。之后呢，会有 $q$ 次独立的询问。每次询问会给你一个点 $P(x, y)$ 的坐标。你需要回答的是，连接原点 $O$ 和点 $P$ 的线段 $OP$ ，会和这 $n$ 个圆中的多少个相交呢？

简单来说，就是对每个点 $P$ ，数一数有多少个圆，它们的“势力范围”能覆盖到线段 $OP$ 的一部分，的说。

解题思路分析

这道题虽然伪装成了几何题，但只要我们稍加分析，就能揪出它算法核心的小尾巴，喵~

步骤一：从几何到数学的华丽转身

首先，我们来想想，“线段 $OP$ 与一个圆相交”到底意味着什么呢？

所有的圆都以原点 $O(0, 0)$ 为中心。线段 $OP$ 也是从原点 $O$ 出发，延伸到点 $P(x, y)$ 。点 $P$ 到原点的距离，根据我们初中学过的勾股定理，是 $d = \sqrt{x^2 + y^2}$ 。

一个半径为 $r$ 的圆，它包含了所有到原点距离小于等于 $r$ 的点。线段 $OP$ 上的任意一点到原点的距离都小于等于 $d$ 。所以，一个半径为 $r$ 的圆要与线段 $OP$ 相交，它的半径 $r$ 必须小于或等于线段 $OP$ 的长度 $d$ 。

也就是说，相交的条件是：

r \le d

或者说：

r \le \sqrt{x^2 + y^2}

步骤二：优雅地避开浮点数陷阱

直接计算 $\sqrt{x^2 + y^2}$ 会涉及到浮点数，不仅计算慢，还可能带来精度问题，本喵可不喜欢这种毛茸茸的麻烦事！一个超级好用的技巧是——两边同时平方！

因为半径 $r$ 和距离 $d$ 都是非负的，所以 $r \le d$ 这个不等式完全等价于 $r^2 \le d^2$ 。

r^2 \le x^2 + y^2

这样一来，我们全程只需要和整数打交道了，是不是很清爽，喵？注意哦， $x, y$ 的值可能很大，它们的平方会超出 int 的范围，所以要用 long long 来存储平方值，防止溢出。

步骤三：从暴力到高效的进化

现在问题转化成了：对于每次查询给出的点 $(x, y)$ ，计算出它的距离平方 $D = x^2 + y^2$ ，然后统计在 $n$ 个圆的半径中，有多少个半径 $r_i$ 满足 $r_i^2 \le D$ 。

最朴素的想法是，每次查询都遍历一遍所有的圆，检查它们的半径平方是否小于等于 $D$ 。这样做一次查询的时间复杂度是 $O(N)$ ，总共 $Q$ 次查询，总时间复杂度就是 $O(N \cdot Q)$ 。如果 $N$ 和 $Q$ 都很大（比如 $10^6$ 级别），这个方法肯定会超时的，就像追不上激光笔的光点一样令人沮丧，呜~

本喵的猫咪直觉告诉我，这里一定有优化的空间！注意到，对于一个固定的半径列表，我们要解决的问题是“在一个集合中，寻找有多少个元素小于或等于某个值”。这是一个非常非常经典的问题模型！当这个集合是有序的时候，我们就可以用二分查找来光速解决它！

最终的完美计划！

所以，我们的高效解法就诞生啦：

预处理 (Preprocessing)：
- 首先，读入所有 $n$ 个圆的半径 $r_i$ 。
- 然后，我们计算出每个半径的平方 $r_i^2$ ，并将这些平方值存入一个数组或向量中（比如叫 radii_squared）。
- 最关键的一步：将这个 radii_squared 数组从小到大排序。
- 这一整个预处理过程的时间复杂度是 $O(N \log N)$ ，只需要做一次。
处理查询 (Handling Queries)：
- 对于每一次查询，我们读入点 $P(x, y)$ 的坐标。
- 计算出距离的平方 $D = x^2 + y^2$ 。
- 现在，我们要在排好序的 radii_squared 数组中，找到有多少个元素小于或等于 $D$ 。
- 使用二分查找！我们可以查找第一个严格大于 $D$ 的元素的位置。假设这个位置的下标是 k，那么下标从 0到 k-1 的所有元素都满足小于或等于 $D$ 的条件。所以，答案就是 k。
- C++ 的 std::upper_bound 函数天生就是为这个任务设计的！upper_bound(begin, end, value) 会返回一个迭代器，指向序列中第一个大于 value 的元素。这个迭代器和数组起始位置的距离，就是我们想要的答案啦！
- 每次查询的时间复杂度是 $O(\log N)$ 。

这样一来，总的时间复杂度就是 $O(N \log N + Q \log N)$ ，对于这道题的数据范围来说，是绰绰有余的，喵~

代码实现

下面是本喵根据上面的思路，精心为你准备的一份代码。它清晰、高效，而且注释满满，希望能帮助你更好地理解，呐！

cpp

#include <iostream>
#include <vector>
#include <algorithm>

// 为了让cin和cout快得像小猫冲刺，喵~
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

int main() {
    fast_io();

    int n; // 圆的数量
    int q; // 询问的数量
    std::cin >> n >> q;

    // 用一个 vector 来存储所有半径的平方值
    // 使用 long long 防止 r*r 溢出
    std::vector<long long> radii_squared(n);
    for (int i = 0; i < n; ++i) {
        long long r;
        std::cin >> r;
        radii_squared[i] = r * r;
    }

    // 关键一步：对半径的平方进行排序，为二分查找做准备
    std::sort(radii_squared.begin(), radii_squared.end());

    // 开始处理 q 次询问
    for (int i = 0; i < q; ++i) {
        long long x, y;
        std::cin >> x >> y;

        // 计算点 P(x, y) 到原点距离的平方
        // 同样使用 long long 防止 x*x 或 y*y 溢出
        long long dist_squared = x * x + y * y;

        // 使用 std::upper_bound 进行二分查找
        // 它的作用是找到第一个 > dist_squared 的元素
        auto it = std::upper_bound(radii_squared.begin(), radii_squared.end(), dist_squared);

        // it 和 radii_squared.begin() 之间的距离，
        // 就是所有 <= dist_squared 的元素的数量
        int count = std::distance(radii_squared.begin(), it);
        
        // 或者更简洁地写成：
        // int count = it - radii_squared.begin();

        std::cout << count << "\n";
    }

    return 0;
}

复杂度分析

时间复杂度: $O(N \log N + Q \log N)$
- 读入 $n$ 个半径并计算平方是 $O(N)$ 。
- 对半径平方数组进行排序，时间复杂度是 $O(N \log N)$ 。
- 处理 $Q$ 次询问，每次询问使用二分查找，时间复杂度是 $O(\log N)$ 。所以 $Q$ 次查询总共是 $O(Q \log N)$ 。
- 总的时间复杂度是这几部分加起来，由最高阶的项决定，即 $O(N \log N + Q \log N)$ 。
空间复杂度: $O(N)$
- 我们主要需要一个额外的数组（或 std::vector）来存储 $N$ 个半径的平方值。所以空间复杂度是 $O(N)$ 。

知识点总结

几何问题转化: 很多计算几何问题，核心是将其转化为代数或数值问题。本题中，"线段与圆相交"被成功转化为了"半径小于等于距离"的数值比较。
避免浮点数: 在处理几何距离或比较大小时，优先考虑使用平方来代替开方，可以避免浮点数计算带来的速度和精度问题。这是个非常实用的小技巧，喵！
识别二分查找模型: "在有序序列中查找满足条件的元素数量"是二分查找的典型应用场景。预处理排序+查询时二分，是一种常见的优化策略。
std::upper_bound 的妙用: C++ STL 提供了强大的算法库。std::upper_bound 是解决此类计数问题的利器，它比手写二分循环更简洁，也更不容易出错。

希望这篇题解能让你有所收获，喵~ 如果还有其他问题，随时可以来问我哦！一起加油，成为更厉害的程序员吧！

[NCT058A]签到题 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

步骤一：从几何到数学的华丽转身 ​

步骤二：优雅地避开浮点数陷阱 ​

步骤三：从暴力到高效的进化 ​

最终的完美计划！ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​