题目描述
假设海岸线是一条无限长的直线，陆地位于海岸线的一边，大海位于海岸线的另一边。大海中有许多小岛。某安全部门为了监视这些岛上是否有敌人入侵，打算在海岸线上安装若干个雷达来检测岛屿的情况。每个雷达的覆盖范围是以雷达中心为圆心，半径为d的圆形区域。
我们用平面之间坐标系来表示整个区域，海岸线为x轴，大海位于x轴上方，陆地位于x轴下方。为了节约成本，安全部门想使用最少的雷达覆盖所有的岛屿。现在已知每个岛屿的坐标(x,y)和雷达的覆盖半径d，你的任务就是计算出能够覆盖所有岛屿的最少雷达数量。
输入输出格式
输入格式：
输入包含若干组数据。每组数据的第一行有两个整数n(1<=n<=1000)和d，分别表示岛屿的数量和雷达的覆盖半径，之后的n行，每行有两个整数，表示第i个岛屿的坐标（xi,yi），相邻的两组数据使用一个空行隔开。输入“0 0”表示输入结束。
输出格式：
对于每一组数据的输出格式为“Case i: x”，表示第i组数据中最少需要x个雷达来覆盖所有的岛屿；x=-1表示这组数据无解（无法覆盖所有的岛屿）
解题思路：
对于x轴上的每个小岛，可以计算出x轴上一段能够管辖它的区间l[i]~r[i]。问题转化为：给定N个区间，在x轴上放置最少的点，使每个区间至少包含一个点。
然后就是贪心操作了，将每个区间按照左端点l[i]从小到大排序，用一个变量来维护已经安放的最后一个监控设备的坐标pos，开始时pos为负无穷。
依次考虑每个区间。如果当前区间i的左端点l[i]大于最后一台监控设备的坐标pos，则新增一台监控设备，并令pos=r[i] （监控尽量向右放），否则就让最后一台已经安放的监控设备来管辖当前区间，并令pos=min(r[i],pos)
for(int i=1;i<=n;i++)
{
if(a[i].l>pos)
{
ans++;
pos=a[i].r;
}
else pos=min(pos,a[i].r);
}
见代码：
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct point{
double l,r;
}a[1005];
int d,bj=0;
bool cmp(const point &x,const point &y){return x.l<y.l;}
void jisuan(int i,double x,double y)
{
double t=d*d-y*y;
if(t<0){bj=1;return;}
a[i].l=x-sqrt(t);
a[i].r=x+sqrt(t);
}
int main()
{
int n,t=0;
while(scanf("%d%d",&n,&d))
{
if(n==0&&d==0)break;
t++;bj=0;
for(int i=1;i<=n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
jisuan(i,x,y);
}
if(bj==1||d<0)
{
printf("Case %d: -1\n",t);
continue;
}
sort(a+1,a+n+1,cmp);
double pos=-0x7fffffff/2;
int ans=0;
for(int i=1;i<=n;i++)
{
if(a[i].l>pos)
{
ans++;
pos=a[i].r;
}
else pos=min(pos,a[i].r);
}
printf("Case %d: %d\n",t,ans);
}
return 0;
}
花开·花落--便是一生 