AcWing 112. 雷达设备
原题链接
中等
作者:
隐灵
,
2024-03-25 17:00:18
,
所有人可见
,
阅读 1
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1010;
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] = {x - len, x + len}; //此为C++11的语法,如果编译失败,就用seg[i].l = x - len,seg[i].r = x + len
}
}
if (failed) puts("-1");
else
{
sort(seg, seg + n);
int cnt = 0;
double last = -1100; //刚开始没有右侧坐标,默认坐标在负无穷的位置上
for (int i = 0; i < n; i ++ )
if (last < seg[i].l) //如果最右边的端点小于下一个线段最左边的端点,就加一个点
{
cnt ++ ;
last = seg[i].r; //让此时的最右端点成为下一个测试点
}
printf("%d", cnt);
}
return 0;
}