circle - 题解

标签与难度

标签: 计算几何, 二分答案, 区间合并, 坐标变换, 浮点数精度难度: 1900

题目大意喵~

主人你好呀~ 这道题是这样的喵：

我们有一个大小为 $n \times m$ 的矩形大盒子，它的左下角在 $(0, 0)$ ，右上角在 $(n, m)$ 。盒子里放了 $k$ 个小豆子（点），而且这些小豆子非常听话，全都排列在一条直线上，喵~

我们的任务是，在这个盒子里找到一个尽可能大的圆形区域，但是这个圆形区域不能严格把任何一个小豆子或者矩形的边给“吃掉”（包含进去）。也就是说，小豆子可以在圆的边界上，圆也可以和矩形的边边相切，但不能越界或者吞掉小豆子哦！

最后，我们需要输出这个最大圆的半径，呐。

解题思路分析

这道题想让我们找一个最大的半径，一看到“最大化某个值”或者“最小化某个值”，我的直觉就告诉我，二分答案很可能是一个好方法，喵！

我们可以二分最终的答案，也就是圆的半径 $R$ 。这样问题就从“求最大半径”转化成了一个判断题：“给定一个半径 $R$ ，是否存在一个合法的圆心 $(c_x, c_y)$ 呢？” 如果我们能解决这个判断问题，那么整个题目就迎刃而解啦。

`check(R)`：给定半径R，是否存在合法圆心？

假设我们二分得到的半径是 $R$ 。一个圆心 $(c_x, c_y)$ 要是合法的，必须满足下面几个条件：

圆必须在矩形内部：这意味着圆心不能太靠近边界。具体来说，圆心 $(c_x, c_y)$ 必须满足 $R \le c_x \le n-R$ 并且 $R \le c_y \le m-R$ 。
圆不能严格包含任何一个给定的点：对于每一个给定的点 $p_i = (x_i, y_i)$ ，圆心 $(c_x, c_y)$ 到它的距离必须大于等于半径 $R$ 。也就是 $(c_x - x_i)^2 + (c_y - y_i)^2 \ge R^2$ 。

把这些条件合起来，我们要在由条件1确定的矩形区域 [R, n-R] x [R, m-R] 内，找到一个点 $(c_x, c_y)$ ，这个点同时还要满足条件2，即位于所有以 $p_i$ 为圆心、半径为 $R$ 的开圆的外部。

直接在二维平面上判断是否存在这样一个点还是太复杂了，喵~ 但别灰心！一个最大化的圆，它一定是被某些东西“卡住”了的，对吧？它很可能是和矩形的某条边相切，或者和某些给定的点相切。

关键简化：圆与矩形边相切

让我们来考虑一种更简单但非常重要的情况：这个最大的圆刚好和矩形的一条边相切。比如说，它和底边 $y=0$ 相切。

如果圆和 $y=0$ 相切，那么它的圆心 $y$ 坐标就必须是 $R$ ！也就是说，圆心一定在直线 $c_y = R$ 上。

这一下就把问题从二维降到一维了，是不是很神奇，喵！现在我们只需要在直线 $c_y = R$ 上找一个合法的 $c_x$ 坐标。

新的条件是：

$c_y = R$ 。为了让圆不超出上边界，我们必须有 $R \le m-R$ ，即 $R \le m/2$ 。
$c_x$ 必须在 $[R, n-R]$ 的范围内。
对于每个点 $p_i = (x_i, y_i)$ ，必须满足 $(c_x - x_i)^2 + (R - y_i)^2 \ge R^2$ 。

我们来化简一下第三个条件：

(c_x - x_i)^2 \ge R^2 - (R - y_i)^2 \\ (c_x - x_i)^2 \ge R^2 - (R^2 - 2Ry_i + y_i^2) \\ (c_x - x_i)^2 \ge 2Ry_i - y_i^2

令 $D_i^2 = 2Ry_i - y_i^2$ 。

如果 $D_i^2 < 0$ （也就是 $y_i > 2R$ 或者 $y_i < 0$ ），这个不等式恒成立，这个点 $p_i$ 对 $c_x$ 没有任何限制。
如果 $D_i^2 \ge 0$ ，那么 $|c_x - x_i| \ge \sqrt{D_i^2}$ 。这意味着 $c_x$ 不能落在区间 $(x_i - \sqrt{D_i^2}, x_i + \sqrt{D_i^2})$ 内。

所以，对于一个给定的半径 $R$ ，每个点 $p_i$ 都会在 $c_y=R$ 这条直线上投下一个“禁止区域”的“影子”。我们的任务就是检查，这些所有点投下的禁止区域，是否把我们本来可选的 $c_x$ 范围 $[R, n-R]$ 给完全覆盖了。

这不就是一个经典的区间覆盖问题了嘛！我们的 check(R) 算法就出来啦：

对于每个给定的点 $p_i$ ，计算出它在 $c_y=R$ 直线上对应的禁止区间。
把所有这些禁止区间收集起来。
将这些区间按左端点排序，然后合并所有重叠的区间。
最后，检查合并后的禁止区间们是否完全覆盖了 $[R, n-R]$ 。如果没有完全覆盖，说明存在一个合法的 $c_x$ ，那么半径 $R$ 就是可行的！

对称的力量：坐标变换

上面的分析是基于“圆与底边相切”的假设。但最大的圆完全可能与顶边、左边或者右边相切呀！

没关系，对称性是我们的好朋友，喵~ 我们可以通过坐标变换，把其他三种情况都变成和“底边相切”一样的问题来处理：

与顶边 y=m 相切：我们可以把整个坐标系沿直线 $y=m/2$ 上下翻转。一个点 $(x, y)$ 就变成了 $(x, m-y)$ 。在这个新坐标系里，原先的顶边 $y=m$ 就变成了新坐标系的底边 $y=0$ 。
与左边 x=0 相切：我们可以把坐标轴交换一下，点 $(x, y)$ 变成 $(y, x)$ ，矩形也从 $n \times m$ 变成 $m \times n$ 。这样，原先的左边 $x=0$ 就变成了新坐标系的底边 $y=0$ 。
与右边 x=n 相切：结合上面两种变换，先交换坐标轴得到 $(y, x)$ ，再对新的 $x$ 坐标做一次翻转，得到 $(y, n-x)$ 。矩形也变成了 $m \times n$ 。

所以，我们的完整策略是：

二分答案半径 $R$ 。
准备四组点集，分别对应原坐标、顶边翻转、左边翻转、右边翻转后的坐标。
在 check(R) 函数中，对这四种情况，分别用我们上面推导的区间覆盖算法进行检查。只要有任何一种情况返回可行，那么半径 $R$ 就是可行的。
根据 check(R) 的结果，调整二分查找的范围，直到找到最精确的 $R$ 。

这样，一个看起来很棘手的几何问题，就被我们一步步分解成了熟悉的二分和区间问题，是不是感觉清晰多啦，喵~

代码实现

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

cpp

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

// 为了精确计算，我们用 double 类型
using ld = long double;

// 定义一个点的结构体，喵~
struct Point {
    ld x, y;
};

// 检查给定半径 R 是否可行
// points: 变换后的点集
// width, height: 变换后矩形的长和宽
bool can_place_circle(ld R, const std::vector<Point>& points, ld width, ld height) {
    // 如果圆的直径比矩形的短边还长，那肯定放不下啦
    if (2 * R > width + 1e-9 || 2 * R > height + 1e-9) {
        return false;
    }

    // 存储由每个点产生的禁止区间
    std::vector<std::pair<ld, ld>> forbidden_intervals;

    for (const auto& p : points) {
        // 我们假设圆心在 y=R 这条线上
        // (cx - p.x)^2 + (R - p.y)^2 >= R^2
        // (cx - p.x)^2 >= 2*R*p.y - p.y*p.y
        ld val = 2 * R * p.y - p.y * p.y;

        // 如果 val < 0，说明这个点离 y=R 的距离已经超过 R 了，构不成威胁
        if (val < 0) {
            continue;
        }

        ld delta_x = sqrt(val);
        forbidden_intervals.push_back({p.x - delta_x, p.x + delta_x});
    }

    // 将禁止区间按左端点排序
    std::sort(forbidden_intervals.begin(), forbidden_intervals.end());

    // 合并重叠的禁止区间
    std::vector<std::pair<ld, ld>> merged_intervals;
    if (!forbidden_intervals.empty()) {
        merged_intervals.push_back(forbidden_intervals[0]);
        for (size_t i = 1; i < forbidden_intervals.size(); ++i) {
            if (forbidden_intervals[i].first <= merged_intervals.back().second + 1e-9) {
                // 如果当前区间和上一个合并后的区间有重叠，就合并它们
                merged_intervals.back().second = std::max(merged_intervals.back().second, forbidden_intervals[i].second);
            } else {
                // 否则，这是一个新的不相交的区间
                merged_intervals.push_back(forbidden_intervals[i]);
            }
        }
    }

    // 检查合法区间 [R, width - R] 是否被完全覆盖
    ld covered_until = R;
    for (const auto& interval : merged_intervals) {
        if (interval.first > covered_until + 1e-9) {
            // 在 covered_until 和 interval.first 之间有空隙！
            // 说明找到了可以放圆心的地方
            return true;
        }
        covered_until = std::max(covered_until, interval.second);
    }

    // 如果所有禁止区间都检查完了，看看覆盖范围是否到达了右边界
    // 如果 covered_until < width - R，说明右边还有空隙
    return covered_until < width - R - 1e-9;
}

// 对一种情况进行二分查找最大半径
ld solve_for_one_case(const std::vector<Point>& points, ld width, ld height) {
    ld low = 0, high = std::min(width, height) / 2.0;
    
    // 二分100次，精度足够了喵~
    for (int i = 0; i < 100; ++i) {
        ld mid = low + (high - low) / 2;
        if (can_place_circle(mid, points, width, height)) {
            // 如果 mid 可行，说明我们可能可以找到更大的半径
            low = mid;
        } else {
            // 如果 mid 不行，说明半径太大了，要缩小
            high = mid;
        }
    }
    return low;
}


int main() {
    // 加速输入输出，让程序跑得更快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    ld n, m;
    int k;
    std::cin >> n >> m >> k;

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

    // 准备四种情况的点集
    std::vector<Point> points_bottom = initial_points;
    std::vector<Point> points_top(k);
    std::vector<Point> points_left(k);
    std::vector<Point> points_right(k);

    for (int i = 0; i < k; ++i) {
        // 顶边翻转
        points_top[i] = {initial_points[i].x, m - initial_points[i].y};
        // 左边翻转 (坐标轴交换)
        points_left[i] = {initial_points[i].y, initial_points[i].x};
        // 右边翻转 (坐标轴交换 + 翻转)
        points_right[i] = {initial_points[i].y, n - initial_points[i].x};
    }
    
    ld max_r = 0;
    
    // 分别计算四种情况下的最大半径，然后取最大值
    max_r = std::max(max_r, solve_for_one_case(points_bottom, n, m));
    max_r = std::max(max_r, solve_for_one_case(points_top, n, m));
    max_r = std::max(max_r, solve_for_one_case(points_left, m, n));
    max_r = std::max(max_r, solve_for_one_case(points_right, m, n));

    // 设置输出精度，美美地输出答案~
    std::cout << std::fixed << std::setprecision(10) << max_r << std::endl;

    return 0;
}

复杂度分析

时间复杂度: $O(C \cdot K \log K)$
- 我们总共对四种情况进行了独立的二分查找。这里的 $C$ 是一个常数，代表我们二分的迭代次数（比如100次）和处理的四种对称情况。
- 在每次二分的 can_place_circle 函数中，主要开销是排序 $K$ 个点产生的禁止区间，复杂度是 $O(K \log K)$ 。
- 合并区间和检查覆盖都是线性时间 $O(K)$ 。
- 所以总的时间复杂度是 $O(4 \cdot 100 \cdot K \log K)$ ，可以简化为 $O(K \log K)$ 。
空间复杂度: $O(K)$
- 我们需要存储 $k$ 个原始点和变换后的点，以及在 can_place_circle 函数中存储最多 $k$ 个禁止区间。所以空间开销与点的数量 $k$ 成正比。

知识点总结

这道题真是一次有趣的冒险，喵！我们用到了好几个强大的工具：

二分答案: 这是解决“最大化/最小化”问题的经典思路。把求解问题变成判定问题，能大大降低思考的复杂度。
降维思想: 通过分析最大圆的性质（很可能与边界相切），我们成功地把一个二维的几何问题，简化成了一维的区间问题，这是解题的关键一步！
坐标变换/对称性: 利用对称性，我们可以把四种不同的情况（与四条边相切）统一成一种模型来处理，避免了写四份几乎重复的逻辑，让代码更优雅，喵~
区间合并: 这是一个非常基础且有用的算法技巧，在处理一维线段覆盖、重叠等问题时非常常见。

希望这篇题解能帮助你更好地理解这道题！继续加油哦，主人！喵~

circle - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

check(R)：给定半径R，是否存在合法圆心？ ​

关键简化：圆与矩形边相切 ​

对称的力量：坐标变换 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​