POJ 1328. Radar Installation(二维贪心)
原题链接
中等
作者:
史一帆
,
2021-07-08 16:39:48
,
所有人可见
,
阅读 227
思路
首先可以明确的是:只要存在任意一个海岛位置超出雷达最大覆盖半径(即y>d),则无解.
在所有海岛的 y<=d 的前提下去思考此问题,
那么此问题的切入点是需要知道【一个雷达要覆盖一个海岛,其可以安装范围是多少】
以海岛坐标(x,y)为圆心,用雷达覆盖半径d画圆,根据前提条件可知,
这个圆与x轴必定存在最少1个(y=d)、最多2个交点(y<d).
可以认为1个交点是2个交点重合的特殊情况,那么这2个交点在x轴上构成的线性区间,
可以看作海岛的被覆盖范围在x轴上的投影 (由此就可以把二维的几何问题转化成一维几何问题)
按照所有海岛的x轴坐标,从小到大依次计算每个海岛在x轴上的投影区间(投影可能存在重叠),
同时把每个雷达抽象成1个点,那么此问题就转化成:
【已知x轴上若干个区间(可能存在交集),现在要往这些区间内放若干个点,
问怎样放置这些点,使得每个区间内至少存在一个点,且所放置的点的总量尽可能最少】
可使用贪心算法求解:
根据每个区间的左端点坐标对所有区间从左到右排序:
① 在左起第一个区间A 的右端点 A.R 放置一个点,总放置点数 P+1
② 若下一个区间B 的左端点 B.L > A.R,
说明 区间A 与 区间B 无交集,此时在区间B 的右端点 B.R 放置一个点,总放置点数 P+1
否则说明 区间A 与 区间B 相交, 此时进一步判断,若 B.R < A.R,
说明 区间B 在 区间A 的内部,此时把原本放置在 A.R 的点移动到 B.R(确保区间B有一个点),总放置点数不变
③ 重复这个过程直到所有区间被遍历完成
代码
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 1010;
struct node {
double l;
double r;
} a[N];
bool cmp(node a, node b) {
return a.l <= b.l;
}
int main() {
int n, d, casei = 0;
while (cin >> n >> d && n && d) {
bool flag = true;
for (int i = 0; i < n; i ++ ) {
double x, y;
cin >> x >> y;
if (y > d)
flag = false;
double z = sqrt(d * d - y * y);
a[i].l = x - z;
a[i].r = x + z;
}
if (!flag)
printf("Case %d: -1\n", ++ casei);
else {
sort(a, a + n, cmp);
int res = 1;
double R = a[0].r;
for (int i = 1; i < n; i ++ ) {
if (a[i].l > R ) {
res ++ ;
R = a[i].r;
} else if (a[i].r <= R)
R = a[i].r;
}
printf("Case %d: %d\n", ++ casei, res);
}
}
return 0;
}