解决方法并不难,贪心算法。对于每一个岛屿,以其坐标为圆心,d为半径作圆,两个交点就是可以安放雷达的范围。取出所有范围,合并可以共用的范围,即是答案。
这道题目给了我几点启发。
- 一定要注意贪心算法的正确性和完整性。
- 对问题要考虑全面。比如d<0的情况。
- stdlib 中的qsort函数中,compare调用一定要返回 int 类型。因此,返回的时候千万不要直接返回double,否则这个double被自动转换过之后就不一定对了。这道题中,return gety0point(zb1) < gety0point(zb2)?-1:1;必须注意。如果换成直接返回他们的差值,就可能出错。
- 该用double的地方就用double,不要习惯性的使用int。
/* * Radar Installation * URL: http://poj.org/problem?id=1328 * Author: Ceeji Cheng * Type: 貪心 * Status: Solved * Visit http://ceeji.net/ for more information. * 2010-11-30 * */ #include <iostream> #include <cstring> #include <cstdlib> #include <cmath> using namespace std; #define maxn 1000 #define dis(x1,y1,x2,y2) pow((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2),0.5) struct xy { int x, y; }; int n, d; xy zb[maxn]; bool cannot = false; inline double gety0point(const xy* zb) { int f = d*d - (zb->y)*(zb->y); if (f < 0) return 9999999; return pow(static_cast<double>(f), 0.5) + zb->x; } inline double gety0point_l(const xy* zb) { int f = d*d - (zb->y)*(zb->y); if (f < 0) return 9999999; return -pow(static_cast<double>(f), 0.5) + zb->x; } int cmp(const void* v1, const void* v2) { const xy* zb1 = static_cast<const xy*>(v1); const xy* zb2 = static_cast<const xy*>(v2); int i = gety0point(zb1), j = gety0point(zb2); if (i == 9999999 || j == 9999999) cannot = true; return gety0point(zb1) < gety0point(zb2)?-1:1; } int main(int argc, char const* argv[]) { int m = 0; while (cin >> n >> d) { ++m; if (n == 0 && d == 0) { return 0; } cannot = false; for (int i = 0; i < n; ++i) { cin >> zb[i].x >> zb[i].y; if (zb[i].y < 0) cannot = true; if (zb[i].y > d) cannot = true; } if (d < 0 || cannot) { cout << "Case " << m << ": -1" << endl; continue; } qsort(zb, n, sizeof(xy), cmp); if (cannot) { cout << "Case " << m << ": -1" << endl; } else { int need = 1; double l = gety0point_l(&zb[0]), r = gety0point(&zb[0]), tmpl; for (int i = 1; i < n; ++i) { tmpl = gety0point_l(&zb[i]); if (tmpl > r) { l = tmpl; r = gety0point(&zb[i]); ++need; } } cout << "Case " << m << ": " << need << endl; } } return 0; } |