POJ1328 Radar Installation(贪心)

题目链接

题意:

给定一坐标系,要求将所有 x轴 上面的所有点,用圆心在 x轴, 半径为 d 的圆盖住。求最少使用圆的数量。

分析:

贪心。

首先把所有点 x 坐标排序, 对于每一个点,求出能够满足的 最靠右的圆心,即雷达的位置。

要保证雷达左面的点都被覆盖,如果不能覆盖就向左移,移到能将左边未覆盖的覆盖。如果后面的店不在雷达的覆盖区,则再加一雷达。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
#include <cmath> using namespace std; const int maxn = + ; struct Pos{
double x, y;
bool operator < (const Pos &rhs) const {
return (x < rhs.x || (x == rhs.x && y > rhs.y));
}
}pos[maxn]; int main() {
int n1, n, d, kase = ;
bool flag;
while(scanf("%d %d", &n1, &d) == ) {
if(n1 == && d == ) break;
n = ;
flag = true;
for(int i=; i<n1; i++) {
cin >> pos[n].x >> pos[n].y;
if(pos[n].y > d) flag = false;
else n++;
} if(d <= ) flag = false; sort(pos, pos+n); int cnt = ;
double t, a, a1; a = pos[].x + sqrt(d*d - pos[].y*pos[].y); for(int i=; i<n && flag; i++) {
double x = pos[i].x, y = pos[i].y; t = d*d - y*y;
a1 = x + sqrt(t); if(x < a && a1 < a)
a = a1;
else if((x-a)*(x-a)+y*y > d*d) {
a = a1;
cnt++;
}
} printf("Case %d: ", ++kase);
if(!flag) printf("-1\n");
else printf("%d\n", cnt);
} return ;
}
上一篇:jquery动态刷新局部表单


下一篇:zoj1360/poj1328 Radar Installation(贪心)