poj1328 Radar Installation

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.

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

Sample Output

Case 1: 2
Case 2: 1

题目大意：假设海岸线是一条无限延伸的直线。陆地在海岸线的一侧，而海洋在另一侧。每一个小的岛屿是海洋上的一个点。雷达坐落于海岸线上，只能覆盖d距离，所以如果小岛能够被覆盖到的话，它们之间的距离最多为d。

题目要求计算出能够覆盖给出的所有岛屿的最少雷达数目。

题目思路：将能放雷达的范围转换成x横坐标的范围，再通过简单排序比较计算需要放置雷达的数量。

#include<iostream>  
#include<math.h>  
#include<algorithm>  
using namespace std;  

  
struct island 
{  
    int x, y;  
}isl[1500];    
  
struct data  
{  
    float sta, end;  
}rad[1500];//用两个结构体存储小岛的横纵坐标和雷达的x起始坐标
  
bool cmp(data a, data b)  
{  
     return a.end < b.end;
}  //定义cmp函数来对雷达的范围以结束位置进行排序
  
int main()  
{  
    int n, d, t = 1;  
    while(cin >> n >> d,n+d)  
    {  
        int i, j, max_y = 0;
        bool vis[1500];    
        for(i = 0; i < n; i ++)  
        {  
            cin >> isl[i].x >> isl[i].y;  
            if(isl[i].y > max_y)  
                max_y = isl[i].y;  
        }  //选出小岛最大的y坐标
          
        cout << "Case " << t ++ << ": ";  
        if(max_y > d || d < 0)  
        {  
            cout << -1 << endl;  
            continue;  //雷达半径不够或者小于0，则输出-1
        }  
        float len;  
        for(i = 0; i < n; i ++)  
        {  
            len = sqrt(1.0 * d * d - isl[i].y * isl[i].y);  
            rad[i].sta = isl[i].x - len;  
            rad[i].end = isl[i].x + len;  
        }  //计算出雷达放置的x的范围，用rad结构体数组存储
        sort(rad, rad + n, cmp); 
          
        int ans = 0;  
        
        memset(vis, false, sizeof(vis));  
        for(i = 0; i < n; i ++)  
        {  
            if(!vis[i])  
            {  
                vis[i] = true;  
                for(j = 0; j < n; j ++)  
                    if(!vis[j] && rad[j].sta <= rad[i].end)  
                        vis[j] = true;  
                ans ++;//从第一个范围开始作为标准，依次比较其他的范围，如果没有访问的范围并且开始x坐标小于 标准范围结束x坐标，则用标志数组标记已访问，
　　　　　　　　　　　　　　　一个循环下来，雷达数量加1，用来探测那些还没有被标记访问的的范围 ，然后以第二个范围作为标准尝试去寻找未被访问的范围一直到所有范围被访问，
　　　　　　　　　　　　　　　最后统计雷达的数量。
            }  
        }  
        cout << ans << endl;  
    }  
    return 0;  
}