Boundary - 题解

标签与难度

标签: 计算几何, 枚举, 哈希表, map, 数学, 浮点数精度难度: 1800

题目大意喵~

你好呀，指挥官！这道题是说，在一个二维平面上，我们有 $n$ 个给定的点，还有一个特殊的老朋友——原点 $(0, 0)$ ，喵~。我们需要找到一个神奇的圆，这个圆的边界（也就是圆周）必须经过原点。在所有满足这个条件的圆里面，我们要找出那个在其边界上包含了最多给定点的圆，并告诉本喵这个最多的点的数量是多少，的说。

简单来说：

输入: 一个整数 $n$ ，和 $n$ 个点的坐标 $(x, y)$ 。
目标: 找一个过原点 $(0, 0)$ 的圆。
要求: 这个圆的圆周上要经过尽可能多的给定点。
输出: 这个最大数量。

举个栗子，如果一个圆经过了原点，还经过了给定的 $P_1, P_3, P_5$ 这三个点，那么它就包含了 3 个点。我们要找到所有可能的圆里，这个数量的最大值，呐。

解题思路分析

喵哈哈，一道计算几何题呢！看起来有点复杂，但别怕，跟着本喵的思路一步步来，很快就能抓住它的尾巴啦！

核心洞察：圆是怎么确定的？

我们都知道，三个不共线的点可以唯一确定一个圆，对吧？题目里有一个非常重要的线索：所有我们考虑的圆都必须经过原点 $O(0, 0)$ 。这可真是个天大的好消息喵！这意味着，确定一个候选圆，我们已经有了一个固定的点 $O$ ，只需要再找两个来自输入点的 $P_i$ 和 $P_j$ 就行啦！

只要 $O, P_i, P_j$ 这三个点不共线，它们就能唯一确定一个圆。

从暴力到巧妙的优化

一个最直接的想法是：

枚举两个点 $P_i$ 和 $P_j$ 。
用 $O, P_i, P_j$ 这三个点确定一个圆。
再检查其他所有点 $P_k$ 是不是也恰好在这个圆上。

这个方法需要三层循环，复杂度是 $O(N^3)$ 。对于 $N$ 高达 2000 的情况，这肯定会超时，跑得比本喵追逗猫棒还慢，不可取！

我们需要更快的办法！不如换个角度思考，喵~？

我们可以固定一个点 $P_i$ ，然后考虑所有经过原点 $O$ 和 $P_i$ 的圆。这样的圆有很多，但如果我们再随便拉一个点 $P_j$ 进来，那么圆 $C_{ij}$ （经过 $O, P_i, P_j$ ）就被确定下来了。

这里的关键点来了，注意听哦！假设除了 $P_j$ 之外，还有另一个点 $P_k$ 也和 $O, P_i$ 在同一个圆上。那么，由 $(O, P_i, P_j)$ 确定的圆，和由 $(O, P_i, P_k)$ 确定的圆，一定是同一个圆！同一个圆，自然就意味着它们有同一个圆心。

Aha! 这就是我们的突破口！

算法“喵”计

我们可以这样做：

我们来枚举每一个点 $P_i$ (从 $0$ 到 $n-1$ )，把它当作我们寻找的“最优圆”上的一个固定点。
对于固定的 $P_i$ ，我们再遍历所有在它之后的点 $P_j$ (从 $i+1$ 到 $n-1$ ，为了不重复计算)。
对于每一对 $(P_i, P_j)$ ，我们计算出那个穿过 $O, P_i, P_j$ 的圆的圆心坐标。
我们用一个 map (或者 unordered_map) 来记录这些圆心出现的次数。map<Point, int> center_counts;。Point 是我们自己定义的表示坐标的结构体。
如果多个不同的 $P_j, P_k, P_l, \dots$ 和固定的 $P_i$ 算出了同一个圆心，就说明这些点 $(P_j, P_k, P_l, \dots)$ 和 $P_i$ 都在同一个过原点的圆上！map 中那个圆心对应的计数值就会增加。
遍历完所有的 $P_j$ 后，我们在 center_counts 中找到出现次数最多的那个圆心。假设它的次数是 max_freq。这意味着，我们找到了一个经过 $O, P_i$ 的圆，它还额外经过了 max_freq 个其他的点。所以，这个圆总共经过了 max_freq + 1 个我们给定的点（别忘了 $P_i$ 自己呀！）。
我们对每个 $P_i$ 都这么做一遍，记录下每次得到的 max_freq + 1 的最大值。这个全局的最大值，就是我们最终的答案啦！

如果 $n \le 1$ ，那答案就是 $n$ 本身，作为特殊情况处理一下就好。对于一般情况，至少有一个点，所以答案最少是 1。

如何计算圆心？

现在只剩下一个数学问题了：已知不共线的三个点 $O(0,0)$ , $P_i(x_i, y_i)$ , $P_j(x_j, y_j)$ ，如何求它们的外接圆圆心 $(c_x, c_y)$ ？

圆心到三个点的距离都相等（都是半径）。利用这个性质，我们可以列出方程：

圆心到 $O$ 的距离的平方: $c_x^2 + c_y^2$
圆心到 $P_i$ 的距离的平方: $(c_x - x_i)^2 + (c_y - y_i)^2$
圆心到 $P_j$ 的距离的平方: $(c_x - x_j)^2 + (c_y - y_j)^2$

令它们相等：

$c_x^2 + c_y^2 = (c_x - x_i)^2 + (c_y - y_i)^2$
$c_x^2 + c_y^2 = (c_x - x_j)^2 + (c_y - y_j)^2$

展开第一个方程： $c_x^2 + c_y^2 = c_x^2 - 2c_x x_i + x_i^2 + c_y^2 - 2c_y y_i + y_i^2$ $0 = -2c_x x_i - 2c_y y_i + x_i^2 + y_i^2$ $2c_x x_i + 2c_y y_i = x_i^2 + y_i^2$ (方程 A)

同理，对第二个方程展开： $2c_x x_j + 2c_y y_j = x_j^2 + y_j^2$ (方程 B)

这是一个关于 $c_x, c_y$ 的二元一次方程组！解这个方程组就能得到圆心坐标啦。用克莱姆法则或者代入消元法都可以解。解出来的结果是：

c_x = \frac{(x_i^2+y_i^2)y_j - (x_j^2+y_j^2)y_i}{2(x_i y_j - x_j y_i)}

c_y = \frac{(x_j^2+y_j^2)x_i - (x_i^2+y_i^2)x_j}{2(x_i y_j - x_j y_i)}

分母 $x_i y_j - x_j y_i$ 正是向量 $\vec{OP_i}$ 和 $\vec{OP_j}$ 的叉积。如果叉积为 0，说明 $O, P_i, P_j$ 三点共线，无法构成一个唯一的圆，这种情况我们要跳过，喵~

好了，理论武装完毕，可以开始写代码啦！

代码实现

这是本喵根据上面的思路，精心重构的一份代码，注释超详细的哦，希望能帮到你，喵~

cpp

#include <iostream>
#include <vector>
#include <cmath>
#include <map>
#include <algorithm>

// 为了处理浮点数，我们需要一个很小的数来判断是否为0
const double EPS = 1e-8;

// 定义一个点结构体，让代码更清晰，喵~
struct Point {
    double x, y;

    // 为了能作为 map 的键，需要重载小于运算符
    bool operator<(const Point& other) const {
        if (std::fabs(x - other.x) > EPS) {
            return x < other.x;
        }
        return y < other.y;
    }
};

int main() {
    // 加速一下输入输出，让程序跑得快一点
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    // 如果点很少，直接就能知道答案啦
    if (n <= 1) {
        std::cout << n << std::endl;
        return 0;
    }

    std::vector<Point> points(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> points[i].x >> points[i].y;
    }

    // 至少有一个点，所以最少能有一个点在圆上
    int max_points_on_circle = 1;

    // 外层循环，固定一个点 Pi
    for (int i = 0; i < n; ++i) {
        // 使用 map 统计由 (O, Pi, Pj) 确定的圆心出现的次数
        std::map<Point, int> center_counts;
        
        // 内层循环，遍历 Pi 之后的所有点 Pj
        for (int j = i + 1; j < n; ++j) {
            double x1 = points[i].x, y1 = points[i].y;
            double x2 = points[j].x, y2 = points[j].y;

            // 计算叉积，作为分母。如果接近0，说明 O, Pi, Pj 共线
            double denominator = 2 * (x1 * y2 - x2 * y1);
            if (std::fabs(denominator) < EPS) {
                continue; // 共线，跳过，不能确定唯一圆
            }

            // d1 = x1^2 + y1^2, d2 = x2^2 + y2^2
            double d1 = x1 * x1 + y1 * y1;
            double d2 = x2 * x2 + y2 * y2;

            // 根据公式计算圆心坐标
            Point center;
            center.x = (d1 * y2 - d2 * y1) / denominator;
            center.y = (d2 * x1 - d1 * x2) / denominator;

            // 对应圆心的计数加一
            center_counts[center]++;
        }

        // 寻找对于当前固定的 Pi，能构成的圆上最多的点数
        int local_max_freq = 0;
        for (auto const& [center, count] : center_counts) {
            if (count > local_max_freq) {
                local_max_freq = count;
            }
        }
        
        // local_max_freq 是除了 Pi 之外的点数，所以总数要加1
        max_points_on_circle = std::max(max_points_on_circle, local_max_freq + 1);
    }

    std::cout << max_points_on_circle << std::endl;

    return 0;
}

复杂度分析

时间复杂度: $O(N^2 \log N)$ 我们有两层嵌套的循环，外层循环 $N$ 次，内层循环平均 $N/2$ 次，所以循环体部分是 $O(N^2)$ 的。在循环内部，我们对 std::map 进行了插入和访问操作，map 的单次操作是 $O(\log K)$ 的，其中 $K$ 是 map 中的元素数量， $K$ 最大为 $O(N)$ 。所以总的时间复杂度是 $O(N^2 \log N)$ ，呐。如果用 std::unordered_map，平均时间复杂度可以优化到 $O(N^2)$ 。
空间复杂度: $O(N)$ 我们主要的额外空间开销是那个 center_counts 的 map。在最坏的情况下，对于一个固定的 $P_i$ ，它和其它所有 $P_j$ 都可能形成不同的圆心，所以 map 的大小会达到 $O(N)$ 。因此，空间复杂度是 $O(N)$ 。

知识点总结

这道题是计算几何入门的好题目，它教会了我们：

转化问题: 将一个看似复杂的“寻找最优圆”问题，通过抓住“三点定圆”和“共圆心”的核心特性，转化为了一个“枚举+计数”的问题。
降维打击: 把 $O(N^3)$ 的暴力想法优化到了 $O(N^2 \log N)$ ，这是算法竞赛中非常重要的思维方式，喵~
几何公式: 学习并应用了如何通过三点坐标（特别是其中一点是原点时）求解外接圆圆心的公式。
数据结构的应用: 巧妙地使用 map 来对非整数（double 类型的坐标）的键进行计数，以识别相同的几何对象（圆心）。
浮点数处理: 在计算几何中，由于精度问题，直接用 == 判断两个浮点数是否相等是危险的。正确的做法是判断它们的差的绝对值是否小于一个极小的数 EPS。

希望这篇题解能让你对计算几何更有信心！继续加油哦，指挥官！喵~

Boundary - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

核心洞察：圆是怎么确定的？ ​

从暴力到巧妙的优化 ​

算法“喵”计 ​

如何计算圆心？ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​