题目描述

假设海岸是一条无限长的直线，陆地位于海岸的一侧，海洋位于另外一侧。每个小岛都位于海洋一侧的某个点上。雷达装置位于海岸线上，且雷达的监测范围为d，当小岛与某雷达的距离不超过d时，该小岛可以被雷达覆盖。我们使用笛卡尔坐标系，定义海岸线为 x轴，海的一侧在 x 轴上方，陆地一侧在 x轴下方。
现在给出每个小岛的具体坐标以及雷达的检测范围，请你求出能够使所有小岛都被雷达覆盖所需的最小雷达数目。

算法思想

代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

class Pairnd implements Comparable<Pairnd>{
    double x;
    double y;
    public Pairnd(double x, double y) {
        super();
        this.x = x;
        this.y = y;
    }
    @Override
    public int compareTo(Pairnd p) {
        // TODO Auto-generated method stub
        return Double.compare(this.y, p.y);
    }


}


public class Main  {


    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String p[]=bufferedReader.readLine().split(" ");
        int n=Integer.parseInt(p[0]);
        int d=Integer.parseInt(p[1]);

        Pairnd a[]=new Pairnd[n];
        boolean flag=false;
        for(int i=0;i<n;i++){
            p=bufferedReader.readLine().split(" ");
            int x=Integer.parseInt(p[0]);
            int y=Integer.parseInt(p[1]);
            if(y>d)flag=true;
            else{
                double t=Math.sqrt(d*d-y*y);
                a[i]=new Pairnd(x-t, x+t);
            }

        }

        for(int i=0;i<n;i++){
            System.out.println(a[i].x+" "+a[i].y);
        }

        if(flag){
            System.out.println(-1);

        }else{
            Arrays.sort(a);
            int res=0;
            double end=-1e20;
            for(int i=0;i<n;i++){
                if(a[i].x > end){
                    res++;
                    end=a[i].y;
                }
            }
            System.out.println(res);
        }

        for(int i=0;i<n;i++){
            System.out.println(a[i].x+" "+a[i].y);
        }

    }

}