Steven_Mengの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$

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
#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);
}

 评论