题目描述

校长想通过监控设备覆盖学校内的n座建筑，每座建筑物被视作一个质点，在笛卡尔坐标系（二维平面坐标）中给出它们的坐标(x, y)，并且所有建筑物均处于x轴的上方。因为学校的供电和传输线路均沿x轴，所以监控设备只被允许建立在x轴上。每台监控设备的监控范围均为一个半径为r的圆形，圆心即为这台设备。
现给出n座建筑物的坐标，问：最少需要几台这样的设备可以实现对所有建筑物的监控？样例解释如下图。

输入

第一行输入n和r (1<=n<=1000)
接下来n行，每行输入两个坐标xi, yi

输出

如果不能监控所有建筑，输出”-1”，否则输出最少台数。

样例输入

3 2
1 2
-3 1
2 1

样例输出

2

思路

首先,将题目进行转化,每个建筑物必须被监控,因此在x轴上,有一个L,R,在[L,R]之间,必须有一台设备
先将建筑物按照R区间,升序排序,然后进行扫描

1. 若该建筑物不被以有监控覆盖,在它的最右边新建一个监控,并枚举之后所有建筑物,如果有建筑物的L<当前的R,那么它可以被新建的监控覆盖,打上标记即可
2. 如果已经被覆盖,跳过即可
3. 注意精度问题

代码

#include <bits/stdc++.h>
using namespace std;

struct node{
    double l,r;
    bool tag;
}a[10005];

bool cmp(node a,node b){
    return (a.r<b.r||a.r==b.r&&a.l>b.l);
}

int n,ans,r,x,y;

int main(){
    cin>>n>>r;
    for (int i=1;i<=n;++i){
        scanf("%d %d",&x,&y);
        if (y>r){
            cout<<-1<<endl;
            return 0;
        }
        double len=sqrt((double)r*r-(double)y*y);
        a[i].l=(double)x-len;
        a[i].r=(double)x+len;
    }
    sort(a+1,a+n+1,cmp);
    for (int i=1;i<=n;++i){
        if (a[i].tag){
            continue;
        }else{
            ans++;
            for (int j=i+1;j<=n;++j){
                if (a[i].r>=a[j].l) a[j].tag=1;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/63/