AcWing 112. 雷达设备
原题链接
中等
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 1010;
// 记录区间左端点右端点
struct thred{
double l, r;
bool operator < (const thred & t )
{
return r < t.r; // 按找右端点排序
}
}a[N];
int main()
{
int n, d, cnt = 0;
bool success = true;
cin >> n >> d;
for(int i = 0;i < n;i++ )
{
int x, y;
scanf("%d%d",&x, &y);
if(y > d) success = false;
double len = sqrt(d * d - y * y);
a[i] = {x - len, x + len}; // 线段左右端点
}
if(!success)
{
puts("-1");
return 0;
}
sort(a,a+n); // 线段排序
// double last = a[0].r;
// cnt++;
// for(int i = 1;i < n;i++)
// {
// if(last < a[i].l)
// {
// last = a[i].r;
// cnt++;
// }
// }
// 上面可以改进一下
double last = -1e10;
for(int i = 0; i < n;i++)
{
if(a[i].l > last)
{
last = a[i].r;
cnt++;
}
}
cout<<cnt<<endl;
return 0;
}