【贪心】[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

3 2
1 2
-3 1
2 1

1 2
0 2

0 0

Sample Output

Case 1: 2
Case 2: 1

题目翻译

我们假设海岸是无限延伸的直线，陆地在海岸的一边，大海在另一边。每个小岛是一个点位于大海那一片区域。详见图片；
每一个雷达的安装位置只能够在海岸线上，只能够覆盖半径为 d 的圆形区域。所以，如果小岛与雷达距离小于等于d才能够覆盖。
我们可以用笛卡尔积坐标系，定义海岸线是 x轴，大海在x 上方，陆地在x 轴下方，给你每个小岛在大海中的位置，并且给出雷达的覆盖范围 d ，你的任务是写一个程序，找到最少需要安装的雷达数量且能够覆盖所有的小岛。一个位置表示 （x，y ）坐标。

Figure A Sample Input of Radar Installations

输入

输入是多组数据；
每行包含两个数 n 和 d；
n 代表小岛的数量，d 代表雷达的覆盖半径；
接下来n行是小岛的位置，用一个二维坐标来表示 Xi， Yi ；
当输入的 n 和 d 都为0， 程序结束。

输出

对于每组数据输出一个答案，每个答案占一行，输出最小需要的雷达数量，如果不能够满足要求，则输出 -1；

分析

首先我想到了这道题是否与岛与x轴的交点有关，于是就以每个岛为圆心，雷达的覆盖半径为半径画圆，找出与x轴的交点。如图。

如果没有交点，就说明雷达覆盖不到，就输出-1。
然后我们就把交点的x坐标算出来，思路如下图。

把圆与x轴的第一个和第二个交点存起来，如果排序后前一个圆的后一个交点大于后一个圆的前一个交点，它们就可以共用一个雷达。
详看代码。

源代码

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,d,x,y,t,ans;
struct node{double p,q;}a[1001];//专门存圆的交点，p为第一个，q为第二个
bool flag,vis[1001];
bool cmp(node x,node y){return x.q<y.q;}
int main()
{
    while(~scanf("%d%d",&n,&d)){
        if(!n&&!d) return 0;
        flag=0;ans=0;memset(vis,0,sizeof vis);
        if(d<0) flag=1;//半径小于0，不符合条件
        for(int i=1;i<=n;i++){
            scanf("%d%d",&x,&y);
            if(y>d) flag=1;//圆与x轴没有交点
            if(!flag){
                double l=sqrt((d*d-y*y)*1.0);
                a[i].p=x-l;a[i].q=x+l;//计算两交点的x坐标
            }
        }
        printf("Case %d: ",++t);
        if(flag){puts("-1");continue;}
        sort(a+1,a+n+1,cmp);//排序
        for(int i=1;i<=n;i++)
            if(!vis[i]){
                vis[i]=1;
                for(int j=1;j<=n;j++)
                    if(!vis[j]&&a[i].q>=a[j].p)//满足条件
                        vis[j]=1;
                ans++;//共用一个雷达
            }
        printf("%d\n",ans);
    }
}