POJ1328 Radar Installation区间贪心

Radar Installation

来源：http://poj.org/problem?id=1328

Time Limit: 1000MS Memory Limit: 10000K

Total Submissions: 112280 Accepted: 24755

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.

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

题意：

就是雷达放x轴上，探测范围为d为半径的圆，小岛在第一第二象限，要你用最少的雷达数覆盖所有小岛。如果其中有一个岛找不到就输出-1。

分析:

1.先要把问题进行转化一下，转化为如果想要探测到小岛，雷达应该放在x轴的哪一个范围内，方法就是以岛为圆心，作半径为d的圆，该圆与x轴的交点间的范围就是要探测该岛雷达可以放置的位置。把这些范围用一条一条的线段表示。

2.把这些线段的左端点按从小到大的顺序排列，为了尽可能使雷达数少，我们可以遍历一条一条的线段，然后记下当前线段的最小右端点，如果接下来出现的线段的左端点比该最小右端点大，则加一个雷达。

3.还需要注意点的坐标可以为小数。

注意：

1、min(current,arr[i].right) 取最小

2、结构体的left right是经过转化后的，是覆盖的坐标范围，不是输入的x y 。经过输入的x,y 再进行转化为left right

代码实现：

//注意更新的时候，current=min(current,arr[i].right)!!!取min
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN=1010;
struct Interval
{
    double left;//坐标可能是小数
    double right;
};
bool compare(Interval x,Interval y)
{
    return x.left<y.left;
}
int main()
{
    Interval arr[MAXN];
    int n,d;
    int casenumber=0;
    while(scanf("%d%d",&n,&d)!=EOF)
    {

        bool flag=true;
        if( n==0 && d==0)
            break;
        for(int i=0;i<n;i++)
        {
            int x,y;
            cin>>x>>y;
            if(y>d)//相离 无论如何安装，固定d后，均不能覆盖到岛屿
                {flag=false;}
            else
                {
                    arr[i].left=x-sqrt(d*d*1.0-y*y);
                    arr[i].right=x+sqrt(d*d*1.0-y*y);
                }
        //输入结束
        //根据分析，按照雷达的左端点按照从小到大排序
        }
        if(flag==false)
            printf("Case %d: %d\n",++casenumber,-1);
        else
        {
             sort(arr,arr+n,compare);//升序
             double current_location=arr[0].right;//因为是按照左端从小到大排列，为了涉及范围更大，把第一个雷达安装在第一个岛屿设计范围的右端点处
             int answer=1;
             for(int i=1;i<n;i++)
             {
                 if(arr[i].left<=current_location)
                 {
                     current_location=min(current_location,arr[i].right);
                     //为什么要取最小的右端点？？min！！！！！！！！！！！！
                     //
                 }else
                 {
                     answer++;
                     current_location=arr[i].right;
                 }
             }
             printf("Case %d: %d\n",++casenumber,answer);
        }
    }
    return 0;
}