这个题题意是说，海上有n多岛，在海岸线上（x轴）建一个雷达能覆盖到与它距离不超过d的岛，求覆盖所有岛的最小雷达数。
当然一上来就有个思路是：
先按x排序再按y排序，每次对于一个岛，找到它最右边允许的造雷达位置，建在那，把所有的这个雷达能覆盖的岛略过。
很显然这是不对的，但是“找到它最右边的位置”却是我们后面用到的思想。
注意到能覆盖每一个岛的范围是一定的。即坐标为x,y的岛只能由[x-sqrt(d*d-y*y),x+sqrt(d*d-y*y)]的雷达覆盖。
所以这个题转化成了，对于所有的区间，求最小的点数能使每个区间都至少有一个点（或许对于这个题是刚好有一个点，但是也没什么不妥…）。
如果区间是传说中的整数，就可以用差分约束系统来搞，但是很显然它不是！所以只好考虑别的方法。
因为是区间，所以考虑区间的关系。也就是几种吧：
这很显然是根据x坐标排序了的。 我们想就是尽可能把雷达放在前面区间的右端点。那么如果后面的区间左端点大于当前右端点，那么就可以覆盖。否则计数+1，从下一个区间重复步骤。
很显然3 和 5 是不符合的。
对于5，我们可以双关键字排序就会略过这种情况。
对于3，它是区间的右端点也大于当前右端点，怎嘛办？
很好办，直接把当前的右端点赋成更小的那一个。
为神马？
因为对于之前的区间，在黑色线段的右端点建立雷达都是可以覆盖的（因为是一直这么做过来的），所以在红色线段的右端点建立雷达也是可以的，而这样使结果更优。
啰嗦太多，上代码……
View Code var f:boolean; p,tim,i,tot,n,d:longint; nowr:real; x,y:array[1..1000] of longint; l,r:array[1..1000] of real;procedure qsort(ll,rr:longint);var t,ml,mr:real; i,j:longint;begin i:=ll; j:=rr; ml:=l[(ll+rr) shr 1]; mr:=r[(ll+rr) shr 1];repeatwhile (l[i]<ml) or ((l[i]=ml) and (r[i]<mr)) do inc(i);while (l[j]>ml) or ((l[j]=ml) and (r[j]>mr)) do dec(j);if i<=j then begin t:=l[i]; l[i]:=l[j]; l[j]:=t; t:=r[i]; r[i]:=r[j]; r[j]:=t; inc(i); dec(j);end;until i>j;if i<rr then qsort(i,rr); if ll<j then qsort(ll,j);end;begin tim:=0;while true do begin readln(n,d); if (n=0) and (d=0) then break; inc(tim); f:=true; p:=n; n:=0;for i:=1 to p dobegin readln(x[i],y[i]);if y[i]>d then begin f:=false; continue; end;if y[i]<0 then continue; inc(n); l[n]:=x[i]-sqrt(sqr(d)-sqr(y[i])); r[n]:=x[i]+sqrt(sqr(d)-sqr(y[i]));end; readln; write('Case ',tim,': ');if f then begin qsort(1,n); i:=1; tot:=0;while i<=n dobegin inc(tot); nowr:=r[i];while (i<n) and (l[i+1]<=nowr) do beginif r[i+1]<nowr then nowr:=r[i+1]; inc(i);end; inc(i);end; writeln(tot);endelse writeln(-1);end;end.转载于:https://www.cnblogs.com/zjerly/archive/2011/10/31/2229871.html
相关资源：poj acm 题解 算法