当前位置：首页 > news >正文

最小半径覆盖问题【C++解法+二分+扫描线】

news 2025/8/4 13:53:41

📌 最小半径覆盖问题【C++解法+二分+扫描线】

🧩 题目描述

在平面上给定 $n$ 个二维点，其坐标分别为 $(x_i, y_i)$。现在需要在坐标平面上以某一点为圆心画一个圆，且圆心必须位于坐标轴上（即 $x$ 轴或 $y$ 轴上），使得该圆能够覆盖不少于 $\lceil \frac{n}{2} \rceil$ 个点。

请你求出满足条件的最小半径。

📥 输入格式

第一行输入一个整数 n，表示点的数量。接下来 n 行，每行输入两个整数 xi 和 yi，表示第 i 个点的坐标。

📤 输出格式

输出一个实数，表示满足要求的最小半径，保留 6 位小数。

✅ 判题要求

设你的输出为 $x$，标准答案为 $y$，当且仅当：

$\leq 10^{-6}$

你的答案将被接受。

📘 输入示例 1

2
0 0
3 4

🎯 输出

0.000000

解释：取圆心为 (0, 0)，半径为 0，即可覆盖第一个点，满足 $k = \lceil \frac{2}{2} \rceil = 1$。

📘 输入示例 2

🎯 输出

0.500000

解释：选圆心为 (1.5, 0)，半径 0.5，能覆盖 (1, 0)、(2, 0)，满足覆盖 $\geq 2$ 个点。

💡 解题思路

本题核心思想是：

二分半径 + 扫描线验证覆盖数量

Step1：半径二分查找

定义二分查找区间：$[0, 3 \times 10^5]$
每次取中值 $mid$，判断是否存在一个圆心在坐标轴上的圆，半径为 $mid$，能覆盖 $\geq k = \lceil \frac{n}{2} \rceil$ 个点。

Step2：扫描线 + 区间合并判断可行性

对于一个给定半径 $r$，判断是否可以用一个圆心在某条坐标轴上的圆覆盖 $\geq k$ 个点：

圆心在 $x$ 轴：若 $|y_i| \leq r$，则点 $(x_i, y_i)$ 可被横轴上的某个圆心覆盖，计算可行的 $x$ 范围区间。
圆心在 $y$ 轴：若 $|x_i| \leq r$，则点 $(x_i, y_i)$ 可被纵轴上的某个圆心覆盖，计算可行的 $y$ 范围区间。
将这些区间看作“事件”，利用扫描线统计同时覆盖最大点数是否 $\geq k$。

🧠 复杂度分析

二分次数为 $O(\log_2(\text{精度})) \approx 60$
每轮中，判断是否可行：$O(n \log n)$（排序 + 扫描）
总体时间复杂度：$O(n \log n \log \text{精度})$

🧾 C++代码实现（附详细注释）

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;typedef pair<double, int> Event;// 检查是否存在一个半径为r的圆，能在坐标轴上找到圆心覆盖至少k个点
bool check(double r, const vector<pair<double, double>>& points, int k) {// 判断横轴或纵轴是否有可行解auto scan = [&](int axis) -> bool {vector<Event> events;for (const auto& [x, y] : points) {if (axis == 0) {  // 圆心在x轴上if (abs(y) > r) continue;double d = sqrt(r * r - y * y);events.emplace_back(x - d, 1);events.emplace_back(x + d, -1);} else {  // 圆心在y轴上if (abs(x) > r) continue;double d = sqrt(r * r - x * x);events.emplace_back(y - d, 1);events.emplace_back(y + d, -1);}}if ((int)events.size() < 2 * k) return false;// 排序：相同位置时，+1 比 -1 优先sort(events.begin(), events.end(), [](const Event& a, const Event& b) {return a.first == b.first ? a.second > b.second : a.first < b.first;});int cnt = 0;for (const auto& [pos, val] : events) {cnt += val;if (cnt >= k) return true;}return false;};return scan(0) || scan(1);
}int main() {int n;cin >> n;vector<pair<double, double>> points(n);for (int i = 0; i < n; ++i) {cin >> points[i].first >> points[i].second;}int k = (n + 1) / 2;  // 至少覆盖一半double lo = 0.0, hi = 3e5;for (int iter = 0; iter < 60; ++iter) {double mid = (lo + hi) / 2;if (check(mid, points, k))hi = mid;elselo = mid;}printf("%.6f\n", hi);return 0;
}