#148. 新校区建设
新校区建设
说明
石家庄二中的新校区建设遇到了一个难题:校长想通过监控设备覆盖学校内的\$N\$座建筑物,以观察和管理同学们的一举一动。而这些设备的控制中心就建在二中的竞赛机房里。于是校长把这个规划任务交给了你。 校园内的每座建筑物被视作一个质点,在笛卡尔坐标系中给出它们的坐标\$(x,y)\$,并且所有建筑物均处在x轴的上方。由于学校的供电和传输线路均沿x轴,所以监控设备只被允许建立在x轴上。
每台监控设备的监控范围均为一个半径为\$R\$的圆形,圆心即为这台设备。现给出\$N\$座建筑物的坐标,问最少需要几台这样的设备可以实现对所有建筑物的监控
输入格式
第一行两个整数\$N,R\$(\$1<=n,r<=1000\$)。
接下来\$n\$行每行两个整数\$x\$(\$|x|<1000\$),\$y(0<=y<=1000)\$,表示建筑物的坐标。
输出格式
如果不能实现对n座建筑物的监控,输出-1,如果能,输出最少需要的监控设备台数。
样例
3 2
1 2
-3 1
2 1
2