[ICPC 2002 Beijing R] 雷达安装

形式化题目

海岸线是 $x$ 轴，海面在 $x$ 轴上方。给出 $n$ 个小岛坐标 $(x_i, y_i)$ （ $y_i \geqslant 0$ ）和雷达半径 $d$ ，雷达只能建在 $x$ 轴上。求覆盖所有小岛所需的最少雷达数；若无法覆盖全部小岛，输出 $-1$ 。

雷达放在 $p$ 处能覆盖小岛 $i$ ，当且仅当

(p-x_i)^2 + y_i^2 \leqslant d^2 .

固定小岛 $i$ 解出 $p$ 的范围：

l_i \leqslant p \leqslant r_i,\qquad l_i = x_i - \sqrt{d^2-y_i^2},\quad r_i = x_i + \sqrt{d^2-y_i^2}.

于是每个小岛对应 $x$ 轴上的一个闭区间，题目等价于：用最少的点刺穿所有区间。当某个 $y_i > d$ 时没有实数 $p$ 满足上式，答案为 $-1$ 。

暴力解法

思路

先把每个小岛转成区间。接下来的关键是限制雷达的候选位置。

右端点引理：存在一个最优解，使得每个雷达都落在某个区间的右端点上。

证明：取一个最优解和一个雷达 $p$ 。只看“仅被 $p$ 覆盖”的那些区间，它们都满足 $p \leqslant r_i$ 。把 $p$ 向右移到这些区间中最小的右端点 $r$ 。此时只被 $p$ 覆盖的区间仍被 $r$ 覆盖（因为 $r \leqslant r_i$ 且 $l_i \leqslant p \leqslant r$ ），同时被其他雷达覆盖的区间不受影响，所以覆盖不变， $p$ 落到了某个右端点。若某个雷达没有“只被它覆盖”的区间，它可以直接删掉。

有了这条引理，候选位置就只剩 $n$ 个右端点。暴力解用 01 序列枚举每个右端点“放 / 不放”雷达：

choose[i] = 1 表示在第 $i$ 个区间的右端点放一个雷达；
递归到叶子后，检查是否每个小岛都被某个已放雷达覆盖；
合法时用雷达数量更新最小值。

这正是 brute.cpp 的写法，它覆盖了所有候选方案，因此答案一定正确。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-09-27 17:28
 * update_at: 2026-09-27 17:30
 */
// brute.cpp：小数据暴力解，使用 01 序列枚举「在哪些小岛区间的右端点放雷达」。
// 每层递归决定第 dep 个区间的右端点是否放雷达，生成完整 choose[1..n] 后在叶子检查。
// 结论：一定存在一个最优解，它的每个雷达都落在某个区间的右端点，所以这样枚举不会漏解。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 25; // 枚举 2^n 种方案，只适合 n 很小的情况
const double EPS = 1e-9;

int n;
double d;
double L[MAXN], R[MAXN]; // 第 i 个小岛对应的雷达可选区间
int choose[MAXN];        // choose[i] = 1 表示在第 i 个区间的右端点放雷达
int ans;

// 检查当前放置方案是否覆盖了所有小岛
bool check() {
    for (int j = 1; j <= n; j++) {
        bool covered = false;
        for (int i = 1; i <= n; i++) {
            // 雷达放在 R[i]，能覆盖小岛 j <=> R[i] 落在 [L[j], R[j]] 内
            if (choose[i] == 1 && L[j] <= R[i] + EPS && R[i] <= R[j] + EPS) {
                covered = true;
            }
        }
        if (!covered) return false;
    }
    return true;
}

// 统计当前方案使用的雷达数量
int calc_answer() {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (choose[i] == 1) cnt++;
    }
    return cnt;
}

void dfs(int dep) {
    if (dep == n + 1) {
        if (check()) {
            int value = calc_answer();
            if (value < ans) ans = value;
        }
        return;
    }

    // 这一层决定第 dep 个区间的右端点要不要放雷达
    for (int v = 0; v <= 1; v++) {
        choose[dep] = v;
        dfs(dep + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> d;
    bool ok = true;
    for (int i = 1; i <= n; i++) {
        ll x, y;
        cin >> x >> y;
        if (y > d) {
            ok = false;
        }
        double half = sqrt(max(0.0, d * d - (double)y * y));
        L[i] = x - half;
        R[i] = x + half;
    }

    if (!ok) {
        cout << -1 << "\n";
        return 0;
    }

    ans = n + 1;
    dfs(1);
    cout << ans << "\n";
    return 0;
}

复杂度

枚举 $2^n$ 个 01 序列，每个序列检查覆盖需要 $O(n^2)$ ，总时间复杂度 $O(2^n \cdot n^2)$ ；空间复杂度 $O(n)$ （区间数组、choose[] 和递归栈）。

瓶颈

瓶颈就是 $2^n$ 的枚举。 $n=30$ 已经无法接受，而题目 $n \leqslant 1000$ 。暴力只适合小数据理解和对拍。

正解

思路

换个角度看：与其在所有右端点的子集里搜索，不如每次只做当下最“急”的那个区间。

把所有区间按右端点 $r$ 从小到大排序。设 last 为最近一个雷达的位置，初始为一个极小的数。按顺序扫描区间：

若当前区间的左端点 $l_i > last$ ，说明已有雷达覆盖不到它，必须新建一个雷达，把它放在这个区间的右端点，并更新 last = r_i；
否则当前雷达已经覆盖它，跳过。

为什么放在右端点最优？设当前还没被覆盖的区间里右端点最小的是 $[l, r]$ 。

任何方案都必须有一个雷达落在 $[l, r]$ 内，否则这个区间无人覆盖；
由于 $r$ 是所有剩余区间中最小的右端点，把那个雷达向右滑到 $r$ 不会丢失任何覆盖；
所以存在最优解把雷达放在 $r$ 。这个雷达顺带覆盖了所有满足 $l_i \leqslant r$ 的区间，剩下的区间再递归处理。

每一步都与某个最优解的第一步一致，所以贪心得到的雷达数就是最小值。

样例推演

样例是 $n=3,\ d=2$ ，三个小岛 (1,2)、(-3,1)、(2,1)。转换并按右端点排序后依次处理：

顺序	区间 $[l_i, r_i]$ （约）	判断	雷达位置 `last`	答案
1	$[-4.73,\ -1.27]$	$l_i > last$ ，新建雷达	$-1.27$	1
2	$[1.00,\ 1.00]$	$l_i > last$ ，新建雷达	$1.00$	2
3	$[0.27,\ 3.73]$	$l_i \leqslant last$ ，已被覆盖	$1.00$	2

第 1 个雷达放在 $-1.27$ ，覆盖 (-3,1)；第 2 个雷达放在 $1.00$ ，同时覆盖 (1,2) 和 (2,1)，所以答案是 2。表里第 3 行说明：排序保证“下一个未覆盖区间”就是剩余区间里右端点最小的，因此一次扫描即可完成贪心。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-09-27 17:28
 * update_at: 2026-09-27 17:30
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 1005;
const double EPS = 1e-9;

int n;
double d;

struct Interval {
    double l, r; // 能覆盖该小岛的雷达横坐标区间 [l, r]
};
Interval a[MAXN];

// 贪心：按区间右端点从小到大排序
bool cmp(const Interval &x, const Interval &y) {
    return x.r < y.r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> d;
    bool ok = true;
    for (int i = 1; i <= n; i++) {
        ll x, y;
        cin >> x >> y;
        if (y > d) {
            // 小岛到海岸线的距离超过雷达半径，任何雷达都覆盖不到
            ok = false;
        }
        // 雷达放在 p 处能覆盖该岛 <=> |p - x| <= sqrt(d^2 - y^2)
        double half = sqrt(d * d - (double)y * y);
        a[i].l = x - half;
        a[i].r = x + half;
    }

    if (!ok) {
        cout << -1 << "\n";
        return 0;
    }

    sort(a + 1, a + n + 1, cmp);

    int ans = 0;
    double last = -1e18; // 最近一个雷达的位置
    for (int i = 1; i <= n; i++) {
        // 左端点在雷达右侧，说明当前雷达覆盖不到这个区间
        if (a[i].l > last + EPS) {
            ans++;
            last = a[i].r; // 把新雷达放在这个区间的右端点
        }
    }
    cout << ans << "\n";
    return 0;
}

复杂度

转换区间 $O(n)$ ，排序 $O(n\log n)$ ，扫描 $O(n)$ ，总时间复杂度 $O(n\log n)$ ；空间复杂度 $O(n)$ 。

总结

本题的核心是把几何问题降维成区间问题：

转化：能覆盖小岛 $i$ 的雷达位置构成区间 $\left[x_i-\sqrt{d^2-y_i^2},\ x_i+\sqrt{d^2-y_i^2}\right]$ ，于是问题变成区间选点；
贪心：按右端点升序扫描，遇到未被覆盖的区间，就把雷达放在它的右端点。

“按右端点排序，尽量往右放”是区间选点、区间调度一类题的标准套路：右端点越小越“急”，越应该先被处理；把点放在右端点，则能覆盖尽可能多的后续区间。