1. 题目
3.Sadar
题目描述：
假设海岸线是一条直线，大海在海岸线的一侧（纵坐标为非负），每个小岛都是海中的一个点，现在在海岸线上安装雷达，所安装的雷达型号相同，即每个雷达所能检测到的范围都是等大的（雷达的检测范围是半径为d的圆）。已知雷达只能建在海岸线上，现在给你n个岛的坐标，假设海岸线为坐标系的x轴，求出最少要建造多少个雷达才能监测到所有的小岛（每个小岛可以被多个雷达监测）。
输入：
输入多组数据。
对于每组数据，第一行输入两个正整数n,d ，分别代表小岛的个数和雷达监测的半径
接下来有n行，每行两个整数x,y 代表小岛的横纵坐标
输出：
对于每组数据，输出最小所需的雷达数，若无法覆盖所有的小岛，输出-1
数据范围：
n<=1000
-maxlongint<=x<=maxlongint
样例：
输入：
3 2
1 2
-3 1
2 1
1 2
0 2
输出：
2
1
2. 题目实质
还记得那个点覆盖区间的贪心不？
3. 算法
贪心。
首先，预处理一下，计算出包含这个点的圆的圆心在哪个区间里，则圆心在这个区间里的圆一定可以包含这个点，这样就转换成了，选取最少的点，使每个区间里都至少有一个点。（如果一个点只能包含一次，那就只能用动规了）
然后关于这个经典模型，这里提供三种解法：
按终点排序，从小到大，选取每一个没有点的区间的右端点（易证，右端点最易在下一个区间内）。
按起点倒序排序，从大到小，选取每一个没有点的区间的右端点。
按起点排序，当一个区间包含另一个区间时，将比较大的那个区间的 y 值赋为较小的区间的 y 值（易证，如果一个点在一个较小的区间里，且一个较大的区间包含这个较小的区间，则这个点一定在那个较大的区间里）。然后再依次选取每个区间的右端点，当后一个区间与前一个区间不包含也不交叉时，将答案加一。
以上三种方法，都是为了避免区间相互包含的情况。
然后就是这样。
4. 注意事项
这个题不是计算几何。
其实，比较难的动规题，是可以用贪心骗分的。
5. 程序代码
Leve 第三种贪心 （Pascal）
var
x,y:array[1..1000] of double;
n,i,j,d,ans,max,xxx,yyy:longint;
tou:double;
procedure qs(r,l:longint);
var
i,j:longint;
xx,yy :double;
begin
i:=r; j:=l;
xx:=x[(i+j)>>1];
repeat
while x[i]<xx do inc(i);
while x[j]>xx do dec(j);
if i<=j then
begin
yy:=x[i]; x[i]:=x[j]; x[j]:=yy;
yy:=y[i]; y[i]:=y[j]; y[j]:=yy;
inc(i);
dec(j);
end;
until i>j;
if i<l then qs(i,l);
if j>r then qs(r,j);
end;
begin
assign(input,'radar.in');
assign(output,'radar.out');
reset(input);
rewrite(output);
readln(n,d);
while (n<>0) and (d<>0) do
begin
max:=0;
for i:=1 to n do
begin
readln(xxx,yyy);
if yyy>max then max:=yyy;
if yyy>d then
begin
for j:=i+1 to n do
readln(xxx,yyy);
break;
end;
x[i]:=xxx-sqrt(sqr(d)-sqr(yyy));
y[i]:=xxx+sqrt(sqr(d)-sqr(yyy));
end;
if max>d then
begin
writeln('-1');
end
else
begin
ans:=1;
qs(1,n);
tou:=y[1];
for i:=2 to n do
if y[i]<tou then
begin
tou:=y[i];
end
else
if x[i]>tou then
begin
tou:=y[i];
inc(ans);
end;
writeln(ans);
end;
readln(n,d);
end;
close(input);
close(output);
end.