传送门
考虑只有一个点,一个雷达的时候,雷达在哪个区间才可以覆盖住这个点,
设dis=d2−y2,发现只有在区间[x−dis,x+dis]才能覆盖住点(x,y),也就是说在[x−dis,x+dis]要至少有一个雷达。
于是题目转换成线段覆盖问题:给你一个数轴和一大堆线段,让你往数轴上面放点,要求每一个线段上面都至少有一个点。
这个问题可以贪心解决,把那些线段按照右端点排序,每次选点都是选右端点,这样为什么是正确的呢?
考虑分情况讨论:
1.l2≤r1
这种情况就不用再新增一个点,因为按照右端点排序保证了r1≤r2,所以l2≤r1≤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); }
|