AcWing 112. 雷达设备(pair实现)
原题链接
中等
作者:
冷丁Hacker
,
2020-10-10 15:53:19
,
所有人可见
,
阅读 506
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
const int N = 1010;
int n, d;
pair<double, double> seg[N];
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;
if (failed == true)
break;
else {
double len = sqrt(d * d - y * y);
seg[i] = make_pair(x +len, x - len);
}
}
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].second) {
// cout<<seg[i].first<<' '<<seg[i].second<<endl;
cnt++;
last = seg[i].first;
}
}
cout << cnt << endl;
}
return 0;
}