问题2902--战争之眼

2902: 战争之眼

时间限制: 1 Sec  内存限制: 128 MB
提交: 87  解决: 24
[状态] [讨论版] [提交] [命题人:]
题目描述

假设战壕是一条无限长的直线,战壕的上方有很多座碉堡。每座碉堡都位于战壕上方的某个点上。我们拥有很多个名为战争之眼的检测装置,战争之眼可以探测出碉堡并进行精确打击,战争之眼均位于战壕上,并且战争之眼的检测范围是以d为半径的圆。


我们使用笛卡尔坐标系,定义战壕为x轴,碉堡位于x轴的上方,战争之眼位于x轴上。


现在给出每个碉堡的具体坐标以及战争之眼的检测范围,请你求出能够使所有碉堡都被战争之眼探索范围覆盖所需的最小战争之眼数目。

输入

第一行输入两个整数 nd,分别代表碉堡数目和雷达检测范围。

接下来n行,每行输入两个整数,分别代表碉堡的xy轴坐标。

数据范围

1<=n<=1000

-1000<=x<=1000

0<=y<=1000

输出

输出一个整数,代表所需的最小战争之眼数目,若没有解决方案则所需数目输出-1

样例输入 Copy
3 2
1 2
-3 1
2 1
样例输出 Copy
2
来源/分类