F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 5166. -- [HAOI2014]遥感监测

5166: [HAOI2014]遥感监测

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 49  Solved: 41
[Submit][Status][Discuss]

Description

外星人指的是地球以外的智慧生命。外星人长的是不是与地球上的人一样并不重要,但起码应该符合我们目前对生
命基本形式的认识。比如,我们所知的任何生命都离不开液态水,并且都是基于化学元素碳(C)的有机分子组合
成的复杂有机体。ZDM实验室的天文学家们已经执著地观测ZDM-99星球十多年了,这个被称为“战神”的红色星球
让他如此着迷。在过去的十多年中,他经常有一些令人激动的发现。ZDM-99星球表面有着明显的明暗变化。对这些
明暗区域,天文学家们已经细致地研究了很多年,并且绘制出了较为详尽的地图,那些暗区是陆地,而亮区则是湖
泊和海洋。他们一直坚信有水的地方,一定有生命的痕迹。这天晚上的观测条件实在是空前的好,ZDM-99星球也十
分明亮,不时呈现出若干个激光点,天文学家们推定这些激光点极有可能存在地球以外的智慧生命。遗憾的是仅持
续很短的一段时间,这些激光点就消失了。ZDM实验室的射电望远镜观测的区域有限,只可以遥感检测到一个半径
为R的圆形区域。为了能同时能检测到所有的激光点,ZDM实验室需要要在一个水平的直线上尽快地安装多个的射电
望远镜来。不妨设,这条安放射电望远镜的水平直线为X轴,ZDM-99星球激光点就处在P1(x1,y1)P2(x2,y2) ,..
.... ,Pn(xn,yn)。(忽略Z坐标)

Input

第1行: N R 分别表示激光点的个数和射电望远镜能检测到的半径
第2~N+1行: Xi Yi 表示 激光点的坐标位置
1≤R≤50 1≤N≤100 -1000≤ Xi Yi ≤ 1000 | Yi | ≤ R
N,R, Xi Yi都是整数。数据之间有一个空格。

Output

最少需要安装的射电望远镜数。

Sample Input

3 2
1 2
-3 1
2 1

Sample Output

2

HINT

Source

[Submit][Status][Discuss]

HOME Back