[C++知识库]POJ 1328 雷达安装

POJ 1328 雷达安装

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const int MAXN=1000+10;     
struct Interval {
    double left;
    double right;
};

Interval arr[MAXN];
bool cmp(Interval a,Interval b){
    return a.left<b.left;
}
int main() {
    int n,d,CaseNumber=0;       //岛屿数目
    while(scanf("%d%d",&n,&d)!=EOF){
        if(n==0&&d==0) break;
        bool flag=true;
        for(int i=0;i<n;++i){
            int x,y;
            scanf("%d%d",&x,&y);
            if(y>d) flag=false;
            else {
                arr[i].left=x-sqrt (double(d*d-y*y));
                arr[i].right=x+sqrt (double(d*d-y*y));
            }
        }
        if(!flag) printf("Case %d: %d\n",++CaseNumber,-1);
        else{                             //区间贪心，根据区间边界点比较
            sort(arr,arr+n,cmp);          //左边界越前，和前面雷达布置范围重叠的可能越大
            double current=arr[0].right;
            int answer=1;
            for(int i=1;i<n;++i){
                if(arr[i].left>current){ 
                    answer++;
                    current=arr[i].right;    //新增雷达则更新雷达布置的右边界
                }else{                       //区间有重叠
                    current=min(current,arr[i].right);   //右边界选择存在重叠部分的最右端，下一个雷达布置的左边界超过前面雷达布置范围的右边界，则雷达++
                }
            }
            printf("Case %d: %d\n",++CaseNumber,answer);
        }      
    }
    system("pause");
    return 0;
}