问题3875--建设小学部

3875: 建设小学部

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

题目描述

金陵河西小学部的新校区建设遇到了一个难题:校长想通过监控设备覆盖学校内的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

来源/分类

 

[提交] [状态]