题目大意，就是令在海岸线的（直线）一边是海(y>0)，另一边是陆地(y<=0)，在海岸线上装雷达，雷达可以覆盖的范围为d，海上有岛，(x,y)，问你应该怎么装雷达，才能做到技能雷达的检测范围覆盖全部的岛，又能使雷达安装最少？（不能做到输出-1）
我的思路，首先是把岛排一次序，然后从x坐标最小的那个岛开始贪心算法，怎么做呢？那就是用x=sqrt(d*d-y*y)+xa,来获得当前岛的安装最远的雷达的位置，然后不断往前找，在超越当前雷达圆心距离之前，不断缩小雷达的位置，使雷达能覆盖到更多的岛，直到岛的横坐标超出雷达中心。
接下来把当前的雷达中心为圆心，把覆盖在圆内的岛全部找出来，这能使一个雷达能覆盖岛最多，然后从最靠近雷达的第一个没被覆盖的岛开始，重复上述过程。
#include <iostream>
#include <functional>
#include <algorithm>
#include <math.h> using namespace std;
typedef double Position;
typedef struct coordinate
{
Position x;
Position y;
}Pos;
int fcmop(const void* a, const void *b)
{
return (*(Pos *)a).x > (*(Pos *)b).x ? : -;
} static Pos islands[];
static bool used[];
int Search(const int, const int);
bool Judge(const int,const int);
double dist(Pos, Position);
Position get_radar_pos(Pos, const int); int main(void)
{
int Sum_Of_Islands, Distance_Of_Radar, k = , ans;
while (~scanf("%d%d", &Sum_Of_Islands, &Distance_Of_Radar))
{
if (Sum_Of_Islands == && Distance_Of_Radar == )
break;
for (int i = ; i < Sum_Of_Islands; i++)
scanf("%lf%lf", &islands[i].x, &islands[i].y);
qsort(islands, Sum_Of_Islands, sizeof(Pos), fcmop);//把岛都按照顺序排序
memset(used, , sizeof(used));
ans = Search(Sum_Of_Islands, Distance_Of_Radar); printf("Case %d: %d\n", k++, ans);
} return ;
} double dist(Pos a, Position mid)//计算两点之间的距离
{
return sqrt((a.x - mid)*(a.x - mid) + a.y*a.y);
} Position get_radar_pos(Pos a, const int dist)
{
Position k = sqrt((double)(dist*dist) - a.y*a.y) + a.x;
return k;
} bool Judge(const int j, const int Distance_Of_Radar)
{
if (islands[j].y - Distance_Of_Radar > )//不可能找到一个雷达覆盖这个岛，直接退出
return ;
else if (islands[j].y < )
return ;
else return ;
} int Search(const int Sum_Of_Islands, const int Distance_Of_Radar)
{
Position tmp_pos, now_min_pos;
int ans = , tmp_mid, j, now_is = ; if (Distance_Of_Radar <= )//Distance小于0，直接再见
return -;
for (; now_is < Sum_Of_Islands;)
{
if (Judge(now_is, Distance_Of_Radar)) return -;
tmp_mid = now_is;
now_min_pos = get_radar_pos(islands[now_is], Distance_Of_Radar);//初始化最远位置
used[now_is] = ;
for (j = now_is + ; j < Sum_Of_Islands && islands[j].x <= now_min_pos; j++)
{
if (used[j]) continue;//必须没被标记过
if (Judge(j, Distance_Of_Radar)) return -;
used[j] = ;//记得标记
tmp_pos = get_radar_pos(islands[j], Distance_Of_Radar);
if (tmp_pos <= now_min_pos)//必须是不能被覆盖才更新
{
now_min_pos = tmp_pos;
tmp_mid = j;//更新是哪一个岛才是中间岛
}
}
ans++;//建立雷达点
for (j = tmp_mid; j < Sum_Of_Islands && islands[j].x <= now_min_pos + Distance_Of_Radar; j++)//把圈内的岛都排除
{
if (Judge(j, Distance_Of_Radar)) return -;
else if (dist(islands[j], now_min_pos) <= Distance_Of_Radar)
used[j] = ;
}
for (j = tmp_mid; j < Sum_Of_Islands && used[j]; j++);//在中心往前找找到第一个没有被标记的点
now_is = j;
}
return ans;
}
代码的变量命名已经能很清楚说明我在干什么了
另外其实代码还可以简化一下，那就是去除used域，其实我们在上面找在雷达圆心右方到那些没被覆盖的岛的时候，我们忽略了其实新的圆也可以与当前作用域重复的，那么我们可以就把used区域去掉，然后把代码改成只要找到在半径外，我们就退出循环。（我就不改了）
另外这一道题其实是挺著名的区间贪婪算法，只是我没有用区间去做而已
要做也很简答，思路就是以岛为圆心，雷达监控范围为半径，画圆，与x轴会有两个交点，然后不断去掉重复区间就可以了，如果有区间是重复的，我们就不断缩小区间，如果区间没有交集了，我们就添加一个雷达，重复步骤
详情见：http://www.cnblogs.com/yu-chao/archive/2011/07/18/2109756.html
另种方法速度差不多，都是O（n）
最近真的是忙死我了，都没什么时间做题，哎