Acwing---112.雷达设备

1.题目

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

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

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

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

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

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

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

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

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

数据范围
$1\le n\le 1000$,
$-1000\le x,y\le 1000$

输入样例：

3 2
1 2
-3 1
2 1

输出样例：

2

2.基本思想

贪心 O(nlogn)

如下图所示，对于任意一个小岛 (x,y)我们都可以在海岸线上求出能覆盖该小岛的建造雷达的区间 [a,b]

由勾股定理可知：

将所有小岛转化成区间后，问题转化为：给定 n 个区间，在 x 轴上选择尽量少的点，使得所有区间至少包含一个点。

算法步骤：

• 1.将所有区间按右端点从小到大排序；
• 2. 依次考虑每个区间：
     如果当前区间包含最后一个选择的点，则直接跳过；
     如果当前区间不包含最后一个选择的点，则在当前区间的右端点的位置选一个新的点；

3.代码实现

import java.util.Arrays;
import java.util.Scanner;public class Main {static Scanner sc = new Scanner(System.in);static int N = 1010;static Pair seg[] = new Pair[N];static double esp = 10e-6;static class Pair implements Comparable<Pair> {double l, r;public Pair(double l, double r) {this.l = l;this.r = r;}@Overridepublic int compareTo(Pair o) {return Double.compare(this.r, o.r);}}public static void main(String[] args) throws Exception {int n = sc.nextInt();//小岛数int d = sc.nextInt();//雷达半径for (int i = 1; i <= n; i++) {int x = sc.nextInt();int y = sc.nextInt();if (y > d) {System.out.println("-1");return;}double len = Math.sqrt(d * d - y * y);//每个岛 投射到x轴上的左、右端点seg[i] = new Pair(x - len, x + len);}//对所有区间 排序Arrays.sort(seg, 1, n + 1);int res = 0;double lastNode = Integer.MIN_VALUE;  //上一个雷达位置//以上一个点的右端点 判断是否在当前区间的左端点内for (int i = 1; i <= n; i++) {if (seg[i].l > lastNode) {   //下一段区间的起始点在上一个雷达的右边 即没有交集 则需要加入新的雷达res++;lastNode = seg[i].r;//更新}}System.out.println(res);}
}