https://vjudge.net/problem/POJ-1328
假设海岸线是一条无限长的直线。陆地在海岸线的一边，海洋在另一边。每个小岛都是位于海边的一个点。
而位于海岸线上的任何雷达装置都只能覆盖 d 的距离，因此，如果两者之间的距离最多为 d，那么海中的一个小岛就可以被一个半径为 d 的装置覆盖。
我们使用直角坐标系，将海岸线定义为 x 轴。海面在 x 轴上方，陆地在 x 轴下方。
给定每个岛屿在海中的位置，并给定雷达装置的覆盖距离，你的任务是编写一个程序，找出覆盖所有岛屿的最小雷达装置数量。
请注意，岛屿的位置由其 x-y 坐标表示。
输入包括几个测试用例。每个案例的第一行包含两个整数 n（1<=n<=1000）和 d，其中 n 是海中岛屿的数量，d 是雷达装置的覆盖距离。
随后是 n 行，每行包含两个整数，分别代表每个岛屿的位置坐标。然后用一行空行来分隔情况。
输入以一行包含一对 0 的行结束
每个测试用例输出一行，包括测试用例编号，以及所需的最少雷达安装数量。"-1 "表示该案例没有解决方案。
3 2
1 2
-3 1
2 1
1 2
0 2
0 0
Case 1: 2
Case 2: 1
通过岛屿圆的半径将半径问题转化为线段贪心问题
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
//https://vjudge.net/problem/POJ-1328
int n, d;
const int N = 1010;
int t = 1;
struct Node {
double l, r;
}nodes[N];
bool cmp(const struct Node& a, const struct Node& b) {
if (a.l > b.l) return true;
return false;
}
void solve() {
sort(nodes,nodes+n,cmp);
int ans = 0; double currl = -99999999; double currr = -99999999;
for (int i = 0; i < n; i++) {
if (nodes[i].l > currr || nodes[i].r < currl) {
ans++; currl = nodes[i].l; currr = nodes[i].r;
}
else {
currl = max(currl, nodes[i].l);
currr = min(currr, nodes[i].r);
}
}
cout << "Case " << t++ << ": " <<ans << endl;
}
int main()
{
while (cin >> n >> d) {
if (n == 0 && d == 0) break;
int flag = 1;
for (int i = 0; i < n; i++) {
int x, y; cin >> x >> y;
if (y < 0) continue;
if (d < y) flag = 0;
double l = x - (double)sqrt((double)d * d - y * y);
double r = x + (double)sqrt((double)d * d - y * y);
nodes[i].l = l; nodes[i].r = r;
}
if (flag == 0) {
cout << "Case " << t++ << ": " << -1 << endl; continue;
}
solve();
}
return 0;
}