基站问题

从前有一个一望无际的海滩，海滩后面是陆地，前面是广阔的大海。海中有很多小岛（可以用一个点表示）。现在海滩上需要安装一些基站（海滩上的任意位置）这样岛上的居民就能用手机通话了，所有的基站的覆盖距离都是d，在距离d范围内的小岛都能收到基站发送的信号。

我们用笛卡尔坐标系来表示这个问题，定义x轴为海滩，x轴上方是大海，下方是陆地。现给出每个小岛的位置（用x-y坐标表示）和基站的覆盖范围d，你的任务就是写一个程序，计算出可以覆盖所有的小岛，至少需要在海滩上安装多少基站？

Input

输入包含多组数据。对每组数据，第一行包含两个整数n（1 <= n <= 1000）和d，n代表小岛数量，d代表基站的覆盖距离。接下来有n行，每行包含两个整数，表示小岛的位置坐标。输入n=0,d=0时退出。

Output

对每组数据，输出包含数据组数，格式如sample，后跟最少需要安装的基站数，如果无解，输出-1。

Sample Input

3 2

1 2

-3 1

2 1

1 2

0 2

1 -2

0 2

0 0

Sample Output

Case 1: 2

Case 2: 1

Case 3: -1







#include<iostream>
#include<algorithm>
#include<math.h>

using namespace std;

#define MAX 1001

struct stuPoint
{
int x;
int y;
};

struct stuLimit
{
double dFrom;
double dTo;
};

stuPoint stuIsland[MAX];
stuLimit stuDuan[MAX];

void vInput(int nN);
bool check(int nN,int nD);
void vSort(int nN);
bool bCmp(const stuLimit &stuA,const stuLimit &stuB);
void vPutOut(int nRet,int Case);
int nGetAns(int nN);

int main()
{
int nIslands,nDistance;
int ans;
int nCase;

nCase=1;
while(2==scanf("%d%d",&nIslands,&nDistance))
{
vInput(nIslands);
if((0==nIslands)&&(0==nDistance))
return 0;
if(check(nIslands,nDistance))
{
vSort(nIslands);
ans=nGetAns(nIslands);
}
else
ans=-1;

vPutOut(ans,nCase);
nCase++;
}

return 0;
}

void vInput(int nN)
{
int i;

for(i=1;i<=nN;i++)
{
scanf("%d%d",&stuIsland[i].x,&stuIsland[i].y);
}

}

bool check(int nN,int nD)
{
int i;

for(i=1;i<=nN;i++)
{
if(stuIsland[i].y>nD)
return false;
stuDuan[i].dFrom=stuIsland[i].x-sqrt(1.0*nD*nD-1.0*stuIsland[i].y*stuIsland[i].y);
stuDuan[i].dTo=stuIsland[i].x+sqrt(1.0*nD*nD-1.0*stuIsland[i].y*stuIsland[i].y);
}
return true;
}

void vSort(int nN)
{
sort(&stuDuan[1],&stuDuan[nN+1],bCmp);
}

bool bCmp(const stuLimit &stuA,const stuLimit &stuB)
{
return(stuA.dFrom<stuB.dFrom);
}

void vPutOut(int nRet,int Case)
{
printf("Case %d: %d\n",Case,nRet);
}

int nGetAns(int nN)
{
int i;
int ans;
int nTemp;

ans=1;
nTemp=stuDuan[1].dTo;
for(i=2;i<=nN;i++)
{

if(nTemp<stuDuan[i].dFrom)
{
nTemp=stuDuan[i].dTo;
ans++;
}
else
{
if(nTemp>stuDuan[i].dTo)
{
nTemp=stuDuan[i].dTo;
}
}

}
return ans;
}