Responsive image

问题 2353 --雷达设备

2353: 雷达设备

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 2
[提交][状态][讨论版][命题人:]

题目描述

假设海岸是一条无限长的直线,陆地位于海岸的一侧,海洋位于另外一侧。

每个小岛都位于海洋一侧的某个点上。

雷达装置均位于海岸线上,且雷达的监测范围为 d,当小岛与某雷达的距离不超过 d 时,该小岛可以被雷达覆盖。

我们使用笛卡尔坐标系,定义海岸线为 x 轴,海的一侧在 xx 轴上方,陆地一侧在 x轴下方。

现在给出每个小岛的具体坐标以及雷达的检测范围,请你求出能够使所有小岛都被雷达覆盖所需的最小雷达数目。

输入描述

第一行输入两个整数 n 和 d,分别代表小岛数目和雷达检测范围。

接下来 n 行,每行输入两个整数,分别代表小岛的 x,y轴坐标。

同一行数据之间用空格隔开。

1≤N≤50000,
1≤A,B≤1000000

输出描述

输出一个整数,代表所需的最小雷达数目,若没有解决方案则所需数目输出 −1

样例输入

3 2
1 2
-3 1
2 1

样例输出

2

来源

[提交][状态]
ACM算法攻关部