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

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 

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.

3 2
1 2
-3 1
2 1

1 2
0 2

0 0

Case 1: 2
Case 2: 1

#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;  
}