#P3737. [HAOI2014] 遥感监测

    ID: 1299 Type: RemoteJudge 1000ms 125MiB Tried: 0 Accepted: 0 Difficulty: 3 Uploaded By: Tags>数学贪心2014河南各省省选

[HAOI2014] 遥感监测

题目描述

外星人指的是地球以外的智慧生命。外星人长的是不是与地球上的人一样并不重要,但起码应该符合我们目前对生命基本形式的认识。比如,我们所知的任何生命都离不开液态水,并且都是基于化学元素碳(C)的有机分子组合成的复杂有机体。

ZDM 实验室的天文学家们已经执著地观测 ZDM-99 星球十多年了,这个被称为“战神”的红色星球让他们如此着迷。在过去的十多年中,他们经常有一些令人激动的发现。ZDM-99 星球表面有着明显的明暗变化。对这些明暗区域,天文学家们已经细致地研究了很多年,并且绘制出了较为详尽的地图,那些暗区是陆地,而亮区则是湖泊和海洋。他们一直坚信有水的地方,一定有生命的痕迹。

这天晚上的观测条件实在是空前的好,ZDM-99 星球也十分明亮,不时呈现出若干个激光点,天文学家们推定这些激光点极有可能存在地球以外的智慧生命。遗憾的是仅持续很短的一段时间,这些激光点就消失了。

ZDM 实验室的射电望远镜观测的区域有限,只可以遥感检测到一个半径为 RR 的圆形区域。为了能同时能检测到所有的激光点,ZDM 实验室需要要在一个水平的直线上尽快地安装多个的射电望远镜来。

不妨设,这条安放射电望远镜的水平直线为 X 轴,ZDM-99 星球激光点就处在 P1(x1,y1),P1(x1,y1),,P1(xn,yn)P_1(x_1,y_1),P_1(x_1,y_1),\cdots,P_1(x_n,y_n)(忽略 Z 坐标)

ZDM 实验室的天文学家们想知道,至少需要安装多少个射电望远镜才能检测到所有激光点。

输入格式

第 1 行,N,RN, R 分别表示激光点的个数和射电望远镜能检测到的半径。

22N+1N+1 行,Xi,YiX_i,Y_i 表示 激光点的坐标位置。

输出格式

输出一行: 最少需要安装的射电望远镜数。

3 2
1 2
-3 1
2 1

2

提示

1R501≤R≤501N1001≤N≤1001000Xi,Yi1000-1000≤ X_i,Y_i ≤ 1000YiR|Y_i| ≤ R

保证输入都是整数。