Radar Installation POJ - 1328

题意：每一个炮台的打击范围为d，现在在x轴上方有n个岛屿（可视为一个坐标），问你在x轴上至少放置几座炮台，从而保证所有岛屿都可以被攻击。如果该目标实现不了，输出-1.
思路：对于每一座岛屿，要想被某一炮台攻击，则这个炮台的安装范围可以确定（如果d < y，显然可以推出无法攻击炮台）。
通过上述操作，可以得到n个（l,r）区间，如下图所示。
通过观察此图，我们发现当$L$L有序时，只需要研究$R$R的变化。
如果$min(R_1,R_2,R_3,...,R_i) < L_{i+1}$min(R1​,R2​,R3​,...,Ri​)<Li+1​
------把一座炮台设置在$min(R_1,R_2,R_3,...,R_i)$min(R1​,R2​,R3​,...,Ri​)处，再确定下一座炮台的位置

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn = 1005;
typedef pair<ll, int> P;
struct node{
	double l, r;
}a[maxn];
bool cmp(node a, node b){
	return a.l < b.l;
}
int n; ll d;
int main(){
	int kase = 0;
	while(scanf("%d%lld", &n, &d), n + d){
		printf("Case %d: ", ++kase);
		bool ok = true; ll x, y;
		for(int i = 1; i <= n; i++){
			scanf("%lld%lld", &x, &y);
			if(y > d){
				ok = false;
				continue;
			}
			double eps = d * d - y * y; eps = sqrt(eps);
			a[i].l = x - eps; a[i].r = x + eps;
		}
		if(!ok){
			printf("-1\n");
		}
		else{
			sort(a + 1, a + n + 1, cmp);
			double mi = a[1].r; int ans = 1;
			for(int i = 1; i <= n; i++){
				if(a[i].l > mi){
					ans++; mi = a[i].r;
				}
				else{
					mi = min(mi, a[i].r);
				}
			}
			printf("%d\n", ans);
		}
	}
	return 0;
}