题意：在坐标轴中给出n个岛屿的坐标，以及雷达的扫描距离，要求在y=0线上放尽量少的雷达能够覆盖全部岛屿。
很明显的区间选点问题。
代码：
/*
* Author: illuz <iilluzen[at]gmail.com>
* Blog: http://blog.****.net/hcbbt
* File: l2911.cpp
* Create Date: 2013-09-09 20:51:05
* Descripton:
*/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std; const int MAXN = 1010;
int n, r, cas = 1; struct Point {
double lhs, rhs;
} a[MAXN]; bool cmp(Point a, Point b) {
if (a.rhs != b.rhs)
return a.rhs < b.rhs;
return a.lhs > b.lhs;
} int main() {
int x, y;
bool flag;
while (scanf("%d%d", &n, &r) && (n || r)) {
flag = true;
memset(a, 0, sizeof(a));
for (int i = 0; i < n; i++) {
scanf("%d%d", &x, &y);
if (flag) {
if (y > r) {
flag = false;
continue;
}
double t = sqrt((double)r * r - y * y);
a[i].lhs = x - t;
a[i].rhs = x + t;
}
}
printf("Case %d: ", cas++);
if (!flag)
printf("-1\n");
else {
sort(a, a + n, cmp);
// for (int i = 0; i < n; i++)
// printf("%lf %lf\n", a[i].lhs, a[i].rhs);
int ans = 1;
double start = a[0].rhs;
for (int i = 1; i < n; i++) {
if (a[i].lhs - start <= 1e-4)
continue;
ans++;
start = a[i].rhs;
}
printf("%d\n", ans);
}
}
return 0;
}