详细看y总写法 https://www.acwing.com/solution/content/1061/
结论:求线段最少需要几个点可以选到全部全部线段
对于每个岛屿有一个线段上的任意雷达都可以覆盖
对于每一个岛屿都一个线段区间,求解最少雷达覆盖就转换为了
最少选择多少个点可以将线段都取到
import java.util.*;
public class Main {
static final int N = 1010;
static ArrayList<double[]> list = new ArrayList<>();
static int n, d;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
d = sc.nextInt();
for (int i = 0; i < n; i++) {
int x = sc.nextInt(), y = sc.nextInt();
if (Math.abs(y) > d) {
System.out.println(-1);
return;
}
double len = Math.sqrt(d * d - y * y);
list.add(new double[]{x - len, x + len});
}
list.sort(Comparator.comparingDouble((o) -> o[1]));
int ans = 1;
double cur = list.get(0)[1];
for (int i = 1; i < list.size(); i++) {
double[] j = list.get(i);
if (j[0] > cur) {
ans ++;
cur = j[1];
}
}
System.out.println(ans);
}
}