本文共 1885 字，大约阅读时间需要 6 分钟。

【题目描述】

【思路】

贪心 有解决方案的前提是：所有小岛都被雷达覆盖即 |yi| <=d 假设岛屿为(x,y),以(x,y)为圆心，半径为d，如果其能被海岸线的雷达(t,0)覆盖，则满足(x - t)^ 2 +y ^ 2 = d^2,t属于[x -sqrt(d * d - y * y)，x+ sqrt(d * d - y * y)]。 每一个岛屿对应x轴上的一条线段，雷达就是线段上的点，从而将二维问题转化为一维问题。 对所有线段按照右区间升序排序，如果所有线段都没有交集那么雷达最小数目就是岛屿个数。当选定一个雷达之后，下一段区间的起始点在上一个雷达的右边，那么这个岛屿就不在 上个雷达的覆盖范围，则需要加入新的雷达

import java.util.Scanner;import java.lang.Math;import java.util.Arrays;class Segment implements Comparable
   
    {       //区间[a,b]    double a, b;    public Segment(double aa, double bb)    {           a = aa;        b = bb;    }    public int compareTo(Segment o)    {            // TODO 自动生成的方法存根        return Double.compare(this.b, o.b);    }}public class Main{       static int N = 1010;    static double INF = 10e8;    static double esp = 10e-6;    static Segment seg[] = new Segment[N];    public static void main(String args[]){           Scanner reader = new Scanner(System.in);        int n = reader.nextInt(), d = reader.nextInt();        boolean success = true;        for(int i = 0; i < n; i++)        {               int x = reader.nextInt(), y = reader.nextInt();            if( Math.abs(y) > d )            {                   success = false;                break;            }            //            double len = Math.sqrt(d * d - y * y);            seg[i] = new Segment(x - len, x + len);        }                if( ! success)            System.out.println( - 1);        else{               //按区间右端点升序排序            Arrays.sort(seg, 0, n);            //上一个雷达位置            double  last = - INF;            int res = 0;            for(int i = 0; i < n; i++)            {                   //下一段区间的起始点在上一个雷达的右边 即没有交集 则需要加入新的雷达                if(seg[i].a -last > esp)                {                       res ++;                    last = seg[i].b;                }                            }            System.out.println(res);        }            }}
   

转载地址：http://xupzz.baihongyu.com/