一、题意：有n个小岛，坐标为(x,y)。以x轴为海岸线，在海岸线上布置雷达，雷达能覆盖半径为d的圆形区域。求最少用多少个雷达能覆盖所有的小岛

 

二、思路：以小岛为圆心，d为半径作圆，其与x轴会有两个交点。这两个交点间的线段，就是满足这题小岛要求的雷达坐标。然后将从这个线段从左到右排序，有交集的线段就表示这两个小岛可以共用一个雷达，从而转换成一个区间贪心的问题。

 

三、代码：

#include"iostream"#include"stdio.h"#include"algorithm"#include"cmath"using namespace std;int n,d;struct Node{    double x,y;};struct InterSection{    double x1,x2;};Node cor[1005];InterSection segment[1005];bool Cmp(const InterSection a,const InterSection b){    if(a.x2!=b.x2) return a.x2
     
      b.x1;}void CalIntersection(int i){    segment[i].x1=sqrt(d*d-cor[i].y*cor[i].y)+cor[i].x;    segment[i].x2=cor[i].x-sqrt(d*d-cor[i].y*cor[i].y);}double Min(double a,double b){    return a
      
       >n>>d,n||d)    {        int ans=0;        for(int i=0;i
       
        >cor[i].x>>cor[i].y;            if(cor[i].y>d) ans=-1;            CalIntersection(i);        }        if(ans!=-1){            sort(segment,segment+n,Cmp);            ans=Solve();        }        cout<<"Case "<<++cnt<<": "<
        
         <