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 题意：N座岛屿，坐标用xi，yi表示，岛屿都位于x轴上。在x轴上建造雷达，每个雷达的的探测范围是以【x，0】为圆心，半径为R的圆（下半圆一看就没用），问最少几个雷达可以探测全部岛屿？ 思路：我们把每个岛屿为圆心，做出x轴上雷达的可行建造区域，那么问题就变成用最小的雷达覆盖最多的区域（每个区域一个雷达）。
我们先将区域按左边界递增排序，每取到一个区间，就记录在这个区间右边界pos，如果下个区间的左边界>pos，说明这个雷达无法探测，需要新建雷达，
否则就pos = min（pos，r），就是让原有的雷达去探测它，但是雷达需要移至两个区间的最小右边界处（交集嘛）。 ①因为要用比较左边界和上一次区间的右边界，所以一定是按照左边界排序的。（这样处理后面的区域和之前区域没啥关系，只和pos有关）
置于为什么pos取右边界，因为右边界代表了雷达最远可放置位置（极值），其包含了区间内可行取值了。（决策包容性？） ②当然如果你反过来，右边界排序，你就需要比较右边界和上一次的左边界也行。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std; int n,r;
struct Node
{
double l,r;
} L[]; double calc(int y,int r)
{
return sqrt(r*r-y*y);
} int dcmp(double a,double b)
{
if(fabs(a-b) < 1e-)
return ;
else
return a-b > ?:-;
}
bool cmp(Node a,Node b)
{
return dcmp(a.l,b.l)<;
}
int main()
{
int cas = ;
while(~scanf("%d%d",&n,&r) && (n || r))
{
int ans=;
for(int i=; i<=n; i++)
{
double x,y;
scanf("%lf%lf",&x,&y);
if(dcmp(y,r) > )
{
ans = -;
continue;
}
double add = calc(y,r);
L[i].l = x-add;
L[i].r = x+add;
}
if(ans == -){printf("Case %d: -1\n",++cas);continue;}
sort(L+,L++n,cmp);
double pos = -0x3f3f3f3f3f3f3f;
for(int i=; i<=n; i++)
{
if(dcmp(L[i].l,pos)>)
{
ans++;
pos = L[i].r;
}
else
{
pos = min(L[i].r,pos);
}
}
printf("Case %d: %d\n",++cas,ans);
}
}