poj 1328 Radar Installation 贪心

男娘i 2021-12-03 16:09 247阅读 0赞

## [**Radar Installation**][Radar Installation] ##

<table style="margin-left:auto;"> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit: 1000MS</strong></td> 
   <td><strong>&nbsp;</strong></td> 
   <td><strong>Memory Limit: 10000K</strong></td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions: 123150</strong></td> 
   <td><strong>&nbsp;</strong></td> 
   <td><strong>Accepted: 27237</strong></td> 
  </tr> 
 </tbody> 
</table>

Description

Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And any radar installation, locating on the coasting, can only cover d distance, so an island in the sea can be covered by a radius installation, if the distance between them is at most d.  
  
We use Cartesian coordinate system, defining the coasting is the x-axis. The sea side is above x-axis, and the land side below. Given the position of each island in the sea, and given the distance of the coverage of the radar installation, your task is to write a program to find the minimal number of radar installations to cover all the islands. Note that the position of an island is represented by its x-y coordinates.  
![1328_1.jpg][]  
Figure A Sample Input of Radar Installations

Input

The input consists of several test cases. The first line of each case contains two integers n (1<=n<=1000) and d, where n is the number of islands in the sea and d is the distance of coverage of the radar installation. This is followed by n lines each containing two integers representing the coordinate of the position of each island. Then a blank line follows to separate the cases.  
  
The input is terminated by a line containing pair of zeros

Output

For each test case output one line consisting of the test case number followed by the minimal number of radar installations needed. "-1" installation means no solution for that case.

Sample Input

3 2
    1 2
    -3 1
    2 1
    
    1 2
    0 2
    
    0 0

Sample Output

Case 1: 2
    Case 2: 1
    
    题意：问最少需要多少个雷达才能覆盖所有小岛
    
    题解：求出每个小岛对应一个雷达的安装区间[l,r],按r从小到大排序，若r相等，按l从大到小排序。

![1468919-20190717145941141-344001809.png][]

#include<iostream>
    #include<algorithm>
    #include<math.h>
    #include<string.h>
    using namespace std;
    struct node
    {
        double l;
        double r;
    }p[1005];
    
    bool cmp(node a,node b)
    {
        if(a.r!=b.r)
            return a.r<b.r;
        else
            return a.l>b.l;
    }
    
    int main()
    {
        int n,d,x,y,t=1,flag;;
        while(scanf("%d%d",&n,&d)&&n&&d)
        {
            flag=0;
            for(int i=0;i<n;i++)
            {
                cin>>x>>y;
                double k;
                k=sqrt((double)d*(double)d-(double)y*y);
                p[i].l=x-k;
                p[i].r=x+k;
                if(y>d||d<0)
                    flag=1;
            }
            if(flag==1)
                printf("Case %d: -1\n",t++);
            else
            {
                sort(p,p+n,cmp);
                double m=p[0].r;
                int cnt=1;
                for(int i=1;i<n;i++)
                {
                    if(p[i].l>m)
                    {
                        cnt++;
                        m=p[i].r;
                    }
                }
                printf("Case %d: %d\n",t++,cnt);
            }
            
        }
    }

转载于:https://www.cnblogs.com/-citywall123/p/11201104.html

[Radar Installation]: http://poj.org/problem?id=1328
[1328_1.jpg]: /images/20211203/f5665dadfcb7431db8e90588456cc992.png
[1468919-20190717145941141-344001809.png]: /images/20211203/159aa0de7970471081cebc3a471390a9.png