AcWing 112. 雷达设备
原题链接
中等
作者:
Bear_King
,
2021-02-02 14:30:07
,
所有人可见
,
阅读 265
贪心策略:
- 将所有区间按照右端点排序
- 扫描每个线段
情况1:如果上一个点不在区间中,则选右端点
情况2:如果上一个点在区间中,跳过
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 1010
using namespace std;
int n,d;
struct Segment
{
double l,r;
bool operator< (const Segment & t) const
{
return r < t.r;
}
}seg[N];
int main()
{
scanf("%d%d",&n,&d);
bool failed = false;
for(int i = 0;i < n;i ++)
{
int x,y;
scanf("%d%d",&x,&y);
if(y > d) failed = true;
else
{
double len = sqrt(d*d - y*y);
seg[i].l = x - len;
seg[i].r = x + len;
}
}
sort(seg,seg + n);
if(failed)
{
puts("-1");
}
else
{
sort(seg,seg+n);
int cnt = 0;
double last = -1e20;
for(int i = 0;i < n;i ++)
if(last < seg[i].l)
{
cnt ++;
last = seg[i].r;
}
printf("%d\n",cnt);
}
return 0;
}