题意:
将一条海岸线看成X轴，X轴上面是大海，海上有若干岛屿，给出雷达的覆盖半径和岛屿的位置，要求在海岸线上建雷达，在雷达能够覆盖全部岛屿情况下，求雷达的最少使用量。
分析：
贪心法，先研究一下每个岛屿，设岛屿到海岸线的垂直距离为d，雷达的覆盖半径为k，若d>k,直接输出-1，若d<=k,则雷达的建造有一个活动区间[x1,x2](用平面几何可以求得出来）。因此，在可以覆盖的情况下每个岛屿都有一个相应的活动区间。该问题也就转变成了最少区间选择问题即：
在n个区间中选择一个区间集合，集合中的各个区间都不相交，集合中元素的个数就是答案了。
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <stdio.h>
using namespace std;
struct point
{
double left, right;
}p[2010], temp;
bool operator < (point a, point b)
{
return a.left < b.left;
}
int main()
{
int n;
double r;
int kase = 0;
while(true)
{
scanf("%d%lf",&n,&r);
if(n==0&&r==0)break;
bool flag = false;
for (int i = 0; i < n; i++)
{
double a, b;
scanf("%lf%lf",&a,&b);
if (fabs(b) > r)
{
flag = true;
}
else
{
p[i].left = a * 1.0 - sqrt(r * r - b * b);
p[i].right = a * 1.0 + sqrt(r * r - b * b);
}
}
cout << "Case " << ++kase << ": ";
if (flag)
{
cout << -1 << endl;
}
else
{
int count = 1;
sort(p, p + n);
temp = p[0];
for (int i = 1; i < n; i++)
{
if (p[i].left > temp.right)//不重叠
{
count++;
temp = p[i];
}
else if (p[i].right < temp.right)//重叠取里面的端点
{
temp = p[i];
}
}
cout << count << endl;
}
}
return 0;
}