将雷达选点问题转化为小岛的区间覆盖为题。
贪心策略:将所有区间按照右端点排序,之后将左端点与当前右端点r0进行比较,若比r0要大,则将r0更新为新的区间的右端点,同时ans++。
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
map<PII,int> mp;
struct node{
double l,r;
bool operator<(const node& p){ //将区间按照右端点从小到大排序
return r<p.r;
}
}a[3000];
double getd(int c,int b) //得到每个小岛覆盖区间
{
double a=c*c-b*b;
return sqrt(a);
}
int idx,n,d,ans;
bool flag;
int main()
{
cin>>n>>d;
int x,y;
for (int i = 1; i <= n; i ++ )
{
cin>>x>>y;
if(y>d) flag=true; //如果该岛太远,则说明不能覆盖所有岛屿
if(!mp[{x,y}])
{
mp[{x,y}]=i;
double L=getd(d,y);
a[idx++]={x-L,x+L}; //将每个小岛的覆盖区间加入数组
}
}
if(flag)
{
puts("-1");
return 0;
}
sort(a,a+idx);
double r0=a[0].r; //当前右端点
ans=1;
for (int i = 1; i < idx; i ++ )
{
if(a[i].l>r0) //当前区间左端点比r0要大,要对右端点进行更新,同时雷达数+1
{
r0=a[i].r;
ans++;
}
// cout<<a[i].l<<" "<<a[i].r<<endl;
}
cout<<ans;
return 0;
}