思路很简单:就是逆向思维,每个点需要的探测器范围,取出n个区间右端点排序,该方法可以找出res个不交集的区间,答案至少需要res个点去探测到每个区间
import java.util.*;
public class Main{
static int N=1010,n;
static class Node implements Comparable<Node>{
double l,r;
Node(double a,double b){
l=a; r=b;
}
public int compareTo(Node o){
if(r>o.r) return 1;
else return -1;
}
}
static Node p[]=new Node[N];
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
int d=sc.nextInt();
for(int i=0;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);
double l=x-len;
double r=x+len;
p[i]=new Node(l,r);
}
Arrays.sort(p,0,n);
int res=0;
double ed=-1e20;
for(int i=0;i<n;i++){
if(p[i].l>ed){
res++;
ed=p[i].r;
}
}
System.out.println(res);
}
}