AcWing 112. 雷达设备
原题链接
中等
作者:
叙利亚悍匪_0
,
2024-03-25 17:26:15
,
所有人可见
,
阅读 1
贪心 区间选点问题
#include<iostream>
#include<math.h>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1010;
struct seg
{
double l,r;
}seg[N];
int n,d;
bool cmp(struct seg s1,struct seg s2)
{
return s1.r<s2.r;
}
int main()
{
cin>>n>>d;
bool failed = false;
for(int i = 0;i<n;i++)
{
int x,y;
cin>>x>>y;
if( y > d) failed = true;
double len = sqrt(d * d - y * y);
seg[i] = {x-len,x+len};
}
sort(seg,seg+n,cmp);
double last = -1e10;
int count = 0;
for(int i = 0;i<n;i++)
{
if(last < seg[i].l)
{
last = seg[i].r;
count++;
}
}
if(failed == true) cout<<"-1"<<endl;
else cout<<count<<endl;
}