POJ 1328 Radar Installation（贪心）

http://poj.org/problem?id=1328

题目大意：

在海岸线上布置雷达来监测岛屿   x轴上方是海洋   下方是陆地    雷达只安置在海岸线上     问要能够监测所有岛屿至少要安置多少个雷达

分析：

按常识平面中雷达的监测范围是一个圆   要知道最少要安置多少雷达   直接将岛屿划分到雷达可监测的区域里是很难实现的    所以我们可以从岛屿出发   看雷达安置在那些地方可以监测到这个岛屿    以岛屿为圆心雷达监测半径为半径做圆    与x轴相交与两点    这两点就是可以放置雷达的区域    然后这个问题就转化成了   求最大不重叠区域的个数（重叠的区域可以用一个雷达，有不重叠的区域就要放一个雷达所以是最大）

AC代码：

#include <stdio.h>
#include <string.h>
#include <cmath>
#include <algorithm>
using namespace std;

struct node{
    int x;
    int y;
}a[1005];
struct fl{
    float left;
    float right;
}count0[1005];
int cmp(fl l,fl r){
    if (l.left==r.left)
        return l.right<r.right;
    return l.left<r.left;
}
int main (){
    int n,d;
    int Case=1;
    while (scanf ("%d%d",&n,&d)&&(n||d)){
        int flag=1;
        for (int i=0;i<n;i++){
            scanf ("%d%d",&a[i].x,&a[i].y);
            if (a[i].y>d){
                flag=0;
            }
        }
        if (!flag){
            printf ("Case %d: -1\n",Case++);
        }
        else{
            for(int i=0;i<n;i++){
                count0[i].left=a[i].x-sqrt(d*d-a[i].y*a[i].y);//   左
                count0[i].right=a[i].x+sqrt(d*d-a[i].y*a[i].y);//   有
            }
            sort(count0,count0+n,cmp);//  按照左端点排序
            int sum=1;
            float temp=count0[0].right;
            for (int i=1;i<n;i++){
                if (count0[i].left>temp){//   没有交集 雷达+1
                    temp=count0[i].right;
                    sum++;
                }
                else {
                    if (count0[i].right<temp){//    找最大的一步
                         temp=count0[i].right;
                    }
                }
            }
            printf ("Case %d: %d\n",Case++,sum);
        }

    }

    return 0;
}