雷达安装(贪心)
雷达安装
题目描述：
假定海岸线是一条无限延伸的直线，陆地在海岸线的一边，大海在另一侧。海中有许多岛屿，每一个小岛我们可以认为是一个点。现在要在海岸线上安装雷达，雷达的覆盖范围是d，也就是说大海中一个小岛能被安装的雷达覆盖，那么它们之间的距离最大为d。
我们使用平面直角坐标系，定义海岸线是x轴，大海在x轴上方，陆地在下方。给你海中每一个岛屿的坐标位置（x,y）和要安装的雷达所覆盖的范围d，你的任务是写一个程序计算出至少安装多少个雷达能将所有的岛屿覆盖。
输入描述：
第一行两个整数n（1≤n≤100000）和d，分别表示海中岛屿的数目和雷达覆盖的范围半径d。
接下来n行，每行两个整数，表示每个岛屿的坐标位置（x,y）。
输出描述：
一行一个整数，即能将所有岛屿全部覆盖至少安装的雷达个数，如果无解则输出“-1”。
样例输入
3 2
1 2
-3 1
2 1
样例输出
点
#include
#include
#include
using namespace std;
typedef struct
{
double lw;
double rw;
} island;//岛交点存储(一开始我还存了x,y坐标,但不必要)
island a[1001];
bool cmp(island s1, island s2)
{
return s1.rw < s2.rw;//sort使用对结构体排序
}
int main()
{
double t;
int n, r, x, y, sum = 1;
cin >> n >> r;
for (int i = 0; i < n; i++)
{
cin >> x >> y;
if (y > r)
sum = -1;//如果无法探测就标记结束吧
t = sqrt(r * r - y * y);
a[i].lw = x - t;
a[i].rw = x + t;//利用勾股算交点
}
if (sum == -1)
{
cout << "-1" << endl;
return 0;
}
sort(a, a + n, cmp);//以右交点为准排序
double temp = a[0].rw;
for (int i = 0; i < n; i++)
{
if (a[i].lw <= temp)//可以探测,忽略
continue;
else
{
sum++;//安置新雷达
temp = a[i].rw;
}
}
cout << sum << endl;
return 0;
}
/* 这道题的分析角度要从岛屿来看,以岛为圆心,雷达探测距离为半径做圆,交岸于两点,将这两点记作左交点和右交点,若雷达在交点区间内就可以探测到
此题选用贪心算法做:贪心策略为将岛屿按右交点升序排序后,在第一个点的右交点处放雷达(刚好测到1号,并且可能兼顾后面的岛)
从第1个岛开始,依次用后面岛的左交点同雷达位置比较,若值小于等于雷达位置,说明雷达处于该岛两交点间,可探测,就跳过这种情况;如果大于雷达位置,则取
该点的右交点作为第二个雷达位置......这样就可以取得最优的结果*/