雷达安装问题

题目描述

假设海岸是一条无限长的直线，陆地位于海岸的一侧，海洋位于另外一侧。

每个小岛都位于海洋一侧的某个点上。

雷达装置均位于海岸线上，且雷达的监测范围为 $d$，当小岛与某雷达的距离不超过 $d$ 时，该小岛可以被雷达覆盖。

我们使用笛卡尔坐标系，定义海岸线为 $x$ 轴，海的一侧在 $x$ 轴上方，陆地一侧在 $x$ 轴下方。

现在给出每个小岛的具体坐标以及雷达的检测范围，请你求出能够使所有小岛都被雷达覆盖所需的最小雷达数目。

输入格式

第一行输入两个整数 $n$ 和 $d$，分别代表小岛数目和雷达检测范围。

接下来 $n$ 行，每行输入两个整数，分别代表小岛的 $x$，$y$ 轴坐标。

同一行数据之间用空格隔开。

输出格式

输出一个整数，代表所需的最小雷达数目，若没有解决方案则所需数目输出 $-1$。

输入输出样例 #1

输入 #1

3 2
1 2
-3 1
2 1

输出 #1

2

输入输出样例 #2

输入 #2

4 3
0 1
2 2
3 1
5 1

输出 #2

2

限制条件

• $1 \le n \le 1000$
• $1 \le d \le 200$
• $-1000 \le x, y \le 1000$

样例解释 #1

小岛坐标：

1. $(1, 2)$
2. $(-3, 1)$
3. $(2, 1)$

雷达监测范围 $d = 2$

首先判断是否有解：如果某个小岛的纵坐标 $|y| > d$，则该小岛无法被任何雷达覆盖，输出 $-1$。

这里所有小岛的纵坐标都 $\le 2$，所以有解。

对于每个小岛 $(x, y)$，可以计算出在海岸线（$x$ 轴）上能够覆盖该小岛的雷达位置区间：

• 雷达到小岛的距离 $\le d$
• 设雷达位置为 $(X, 0)$，小岛位置为 $(x, y)$
• 距离公式：$\sqrt{(X - x)^2 + y^2} \le d$
• 解得：$X \in [x - \sqrt{d^2 - y^2}, x + \sqrt{d^2 - y^2}]$

对于样例1：

1. 小岛1 $(1, 2)$：$d^2 - y^2 = 4 - 4 = 0$，区间 $[1, 1]$
2. 小岛2 $(-3, 1)$：$\sqrt{4 - 1} = \sqrt{3} \approx 1.732$，区间 $[-4.732, -1.268]$
3. 小岛3 $(2, 1)$：区间 $[0.268, 3.732]$

现在问题转化为：在数轴上有若干个区间，选择最少的点，使得每个区间内至少有一个点。

使用贪心算法：

1. 将所有区间按右端点从小到大排序
2. 遍历每个区间：
   • 如果当前区间的左端点 > 上一个雷达的位置，则需要新建一个雷达，雷达位置设在该区间的右端点
   • 否则，当前区间可以被上一个雷达覆盖

对于排序后的区间：

1. 小岛2：$[-4.732, -1.268]$
2. 小岛1：$[1, 1]$
3. 小岛3：$[0.268, 3.732]$

贪心过程：

• 第一个雷达：放在区间1的右端点 $-1.268$
• 区间2：左端点 $1 > -1.268$，需要新雷达，放在区间2的右端点 $1$
• 区间3：左端点 $0.268 < 1$，可以被第二个雷达覆盖

需要2个雷达，输出2。