洛谷P1325 雷达安装 题解

题目链接：P1325 雷达安装 & UVA1193

题意：

假设海岸线是一条无限延伸的直线。它的一侧是陆地，另一侧是海洋。每一座小岛是在海面上的一个点。雷达必须安装在陆地上（包括海岸线），并且每个雷达都有相同的扫描范围 \(d\)。你的任务是建立尽量少的雷达站，使所有小岛都在扫描范围之内。

数据使用笛卡尔坐标系，定义海岸线为 \(x\) 轴。在 \(x\)​ 轴上方为海洋，下方为陆地。

输入格式：

第一行包括 \(2\) 个整数 \(n\) 和 \(d\)，\(n\) 是岛屿数目，\(d\) 是雷达扫描范围。

接下来 \(n\) 行，每行两个整数，为岛屿坐标。

输出格式：

一个整数表示最少需要的雷达数目，若不可能覆盖所有岛屿，输出 -1。

数据范围：

对于全部数据，\(n\le1000,~d \le 2\times 10^4,~ | x_i | \le 2 \times 10^6,~ 0 \le y_i \le 2\times 10^4\)。

考察如何圆的位置不是很方便，但是我们可以计算出每个点最远可以在哪放圆

设这个区间为 \([l,r]\) ，则 \(l = x_i - \sqrt{d^2-y^2},~r=x_i - \sqrt{d^2+y^2}\)

那么问题就转化为了，区间上有若干条线段，要找最小的集合数使得每个集合内的线段相交。

这个我们可以直接贪心扫过去，因为任何一条线都一定会加入某个集合。

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e3 + 15))

struct node { double l, r; } a[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, d; cin >> n >> d; bool ok = true;
    for(int i = 1, x, y; i <= n; i++)
    {
        cin >> x >> y; if(abs(y) > d) ok = false;
        a[i].l = x - sqrt(d * d - y * y);
        a[i].r = x + sqrt(d * d - y * y);
    }
    if(!ok) { return cout << "-1\n", 0; }
    sort(a + 1, a + 1 + n, [](node a, node b) { return a.l < b.l; });
    double R = a[1].r; int res = 1;
    for(int i = 2; i <= n; i++) {
        if(a[i].l <= R) R = min(R, a[i].r); else { R = a[i].r, ++res; }
    }
    cout << res << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/xkvpnqo6

---

题外话：

应该放张图活跃气氛。