Radar Installation

傷城~ 2022-07-16 01:15 154阅读 0赞

Radar Installation

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong> 1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong> 10000K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong> 77760</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong> 17398</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

Source

[Beijing 2002][]

#include<iostream>
    #include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    #include<algorithm>
    using namespace std;
    
    struct node
    {
        double l;
        double r;
    } a[1010];
    
    bool comp(node a,node b)
    {
        if(a.r<b.r)
            return true;
    
        else if(a.r==b.r)
        {
            if(a.l>b.l)
                return true;
            return false;
        }
        return false;
    }
    
    int main()
    {
        int num;
        int i,n;
        int cas=1;
        int x,d,y;
        double temp;
        while(~scanf("%d %d",&n,&d)&&(n||d))
        {
            int flag=1;
            num=1;
    
    
            for(i=0; i<n; i++)
            {
                scanf("%d %d",&x,&y);
                temp=(double)(d*d-y*y);
                if(temp<0||d<0)
                {
                    flag=0;
                }
                else
                {
                    a[i].l=x-sqrt((double)d*d-y*y);
                    a[i].r=x+sqrt((double)d*d-y*y);
                }
            }
    
            if(!flag)
            {
                printf("Case %d: -1\n",cas++);
                continue;
            }
            else
            {
                sort(a,a+n,comp);
                temp=a[0].r;
                for(i=1; i<n; i++)
                {
                    if(a[i].l>temp)
                    {
                        temp=a[i].r;
                        num++;
                    }
                }
                printf("Case %d: %d\n",cas++,num);
            }
    
        }
        return 0;
    }

[1328_1.jpg]: http://poj.org/images/1328_1.jpg
[Beijing 2002]: http://poj.org/searchproblem?field=source&key=Beijing+2002