Steven_Meng's Blog

传送门

考虑只有一个点，一个雷达的时候，雷达在哪个区间才可以覆盖住这个点，

设$dis=\sqrt{d^2-y^2}$，发现只有在区间$[x-dis,x+dis]$才能覆盖住点$(x,y)$，也就是说在$[x-dis,x+dis]$要至少有一个雷达。

于是题目转换成线段覆盖问题：给你一个数轴和一大堆线段，让你往数轴上面放点，要求每一个线段上面都至少有一个点。

这个问题可以贪心解决，把那些线段按照右端点排序，每次选点都是选右端点，这样为什么是正确的呢？

考虑分情况讨论：

1.$l2 \le r1$

这种情况就不用再新增一个点，因为按照右端点排序保证了$r1 \le r2$，所以$l2 \le r1 \le r2$，所以选的点$r1$在区间$[l2,r2]$之内。

2.$l2 > r1$

这种情况再怎么样也是要新增一个点的，所以$ans++$

具体实现的时候，维护一个$now$的指针，表示现在已经覆盖到哪里了。

注意$y>d$的时候要输出$-1$

#include <bits/stdc++.h>
#define MAXN 2000005
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
struct node{double l,r;}p[MAXN];
inline bool operator < (const node &A,const node &B){
    return A.r<B.r;
}
int main(){
    int n=read(),d=read();
    for (register int i=1;i<=n;++i){
        int x=read(),y=read();
        if ((double)y>d){
            printf("-1\n");
            return 0;
        }
        const double dis=sqrt(d*d-y*y);
        p[i].l=(double)(x)-dis;
        p[i].r=(double)(x)+dis;
    }
    sort(p+1,p+1+n);
    double now=p[1].r;int ans=1;
    for (register int i=2;i<=n;++i){
        if (now<p[i].l){
            ans++,now=p[i].r;
        }
    }
    printf("%d\n",ans);
}