POJ 1328 Radar Installation(贪心)

比眉伴天荒 2022-05-17 01:25 135阅读 0赞

[题目链接][Link 1]

题意：以x轴为分界，y>0的部分是海，y<0的部分是陆地，给出一些岛屿坐标（在海中），再给出雷达的半径范围，雷达只可以安在陆地和x轴上，问最少需要多少雷达可以覆盖所有岛屿，如果不能就输出-1。

分析：因为雷达是不固定的，但是每个岛屿是固定的，以每个岛屿(x，y)为圆心，以雷达半径为半径作圆，与x轴的左交点即为

x-（r²-y²），与x轴的右交点为x+（r²-y²），那么每个雷达只要安放在左右交点之间（包括交点），则就可以覆盖这个岛屿，那么这题就转换为了求不相交区间的个数，首先将每组端点按左交点由小到大排序，如果下组端点的左端点大于当前端点的右端点，那么就需要再增加一个雷达，如果下组端点的左端点小于当前端点的右端点，则分为两种情况：1.如果下组端点的右端点也小于当前端点的右端点，即下组端点被当前端点所包含，就将下组端点作为当前标注，换个图可以看出来。2.如果下组端点的右端点大于等于当前端点的右端点，那么就还是以当前这组端点作为标准。

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<cctype>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    #define inf 0x3f3f3f3f
    #define maxn 2005
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    using namespace std;
    const double pi=acos(-1.0);
    int n;
    double r;
    
    struct node{
        double l,r;
        bool operator<(const node a)const{
            return l<a.l;
        }
    }arr[maxn];
    
    int main()
    {
        int kase=0;
        while(scanf("%d%lf",&n,&r)&&(n||r))
        {
            double a,b;
            int flag=1;
            fup(i,0,n)
            {
                scanf("%lf%lf",&a,&b);
                if(fabs(b)>r)
                    flag=0;
                 else{
                    arr[i].l=a*1.0-sqrt(r*r-b*b);
                    arr[i].r=a*1.0+sqrt(r*r-b*b);
                 }
            }
            printf("Case %d: ",++kase);
            if(!flag) printf("-1\n");
            else{
                int ans=1;
                sort(arr,arr+n);
                node temp=arr[0];
                fup(i,1,n){
                    if(arr[i].l>temp.r){
                         ans++;
                         temp=arr[i];
                    }else  if(arr[i].r<temp.r)  temp=arr[i];
                }
                printf("%d\n",ans);
            }
        }
        return 0;
    }

[Link 1]: http://poj.org/problem?id=1328