题目链接

题意

在\(x\)轴上方有\(n\)个海岛，要在\(x\)轴建雷达，每个雷达的覆盖范围为半径为\(d\)的圆，问至少要建多少个雷达能覆盖所有海岛。

思路

对于每个海岛计算出雷达建立在什么范围（\(x\)轴上的一条线段）内能覆盖到它。排序并计算线段的交。

Code

#include <bits/stdc++.h>

#define inf 0x3f3f3f3f

#define maxn 200010

using namespace std;

typedef long long LL;

struct node {

    double l, r;

}a[maxn];

int x[maxn], y[maxn];

bool cmp(node u, node v) {

    return u.l < v.l || (u.l == v.l && u.r < v.r);

}

int main() {

    int n, d;

    scanf("%d%d", &n, &d);

    for (int i = 0; i < n; ++i) scanf("%d%d", &x[i], &y[i]);

    for (int i = 0; i < n; ++i) {

        if (y[i] > d) { printf("-1\n"); return 0; }

        double dx = sqrt(pow(d,2)-pow(y[i],2));

        a[i].l = x[i] - dx, a[i].r = x[i] + dx;

    }

    sort(a, a+n, cmp);

    double l = -inf, r = -inf;

    int cnt = 0;

    for (int i = 0; i < n; ++i) {

        if (a[i].l <= r) l = max(l, a[i].l), r = min(r, a[i].r);

        else ++cnt, l = a[i].l, r = a[i].r;

    }

    printf("%d\n", cnt);

    return 0;

}

巴特西

luogu 1325 雷达安装

题目链接

题意

思路

Code

最新文章

热门文章