AcWing 112. 雷达设备
原题链接
中等
作者:
SuperN0vA
,
2024-11-06 14:21:04
,
所有人可见
,
阅读 1
#include<bits/stdc++.h>
using namespace std;
typedef pair<double, double> PDD;
const int N = 1010;
const double eps = 1e-6, INF = 1e10;
int n, d;
PDD seg[N];
int main()
{
cin >> n >> d;
bool success = true;
for (int i = 0; i < n; i++)
{
int x, y;
cin >> x >> y;
if (y > d) // 因为雷达只能建在坐标轴上,如果小岛的y坐标大于雷达范围,就说明不存在解
{
success = false;
break;
}
auto len = sqrt(d * d - y * y);
seg[i] = {x + len, x - len};
}
if(!success) puts("-1");
else
{
sort(seg, seg + n);
int res = 0;
double last = -INF;
for (int i = 0; i < n; i++)
{
if (seg[i].second > last + eps)
{
res ++;
last = seg[i].first;
}
}
cout << res << endl;
}
return 0;
}