先求出所有小岛x_i,y_i在半径为d的情况下映射到x轴的范围[l_i,r_i],雷达在[l_i,r_i]的任意一个点上都能覆盖对应的小岛
记录最后一个雷达的位置pos,再对[l_i,r_i]进行排序后依次取:
1. 若l_i > pos,那么就需要新建一个雷达,为了让雷达尽量覆盖,取pos = r_i
2. 若l_i < pos, 则表示当前雷达可以覆盖当前的小岛,取pos = min(pos, r_i),为什么取min呢,因此有可能r_i < pos, 此时必须将pos设置为r_i才能覆盖当前小岛,又因为l_i > l_i-1, r_i > l_i,因此r_i > l_i-1,所有移动pos不会对之前覆盖的小岛产生影响
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
public class Main {
static List<Pairs> islands = new ArrayList<>();
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int d = scanner.nextInt();
for (int i = 0; i < n; i++) {
int x = scanner.nextInt();
int y = scanner.nextInt();
if (y > d) {
System.out.println(-1);
return;
} else {
double l = x - Math.sqrt(Math.pow(d,2) - Math.pow(y, 2));
double r = x + Math.sqrt(Math.pow(d,2) - Math.pow(y, 2));
islands.add(new Pairs(l, r));
}
}
Collections.sort(islands);
double radarPos = Integer.MIN_VALUE;
int res = 0;
for (Pairs pairs : islands) {
if (pairs.left > radarPos) {
res++;
radarPos = pairs.right;
} else {
radarPos = Math.min(pairs.right, radarPos);
}
}
System.out.println(res);
}
}
class Pairs implements Comparable<Pairs> {
double left;
double right;
public Pairs(double left, double right) {
this.left = left;
this.right = right;
}
@Override
public int compareTo(Pairs o) {
return (int) (this.left - o.left);
}
}