(贪心5.2.4)ZOJ 1360 Radar Installation(对有序化数据进行贪心选择)

本题在POJ上貌似无法通过

/* * POJ_1328.cpp * *  Created on: 2013年10月10日 *      Author: Administrator */#include <iostream>#include <cstdio>#include <cmath>#include <algorithm>using namespace std;const int maxn = 1010;int n,d;struct tt {double l, r;} p[maxn];void init() {int i;double x, y,h;for (i = 1; i <= n; ++i) {scanf("%lf%lf", &x, &y);if (y > d) {d = -1;return;}h = sqrt(d * d - y * y);p[i].l = x - h;p[i].r = x + h;}}bool cmp(tt a, tt b) {if (a.r < b.r) {return true;}if ((a.r == b.r) && (a.l < b.l) ) {return true;}return false;}void work() {int i;if (d == -1) {printf("-1\n");return;}sort(p + 1, p + 1 + n, cmp);int ans = 0;double last = -100000000;for (i = 1; i <= n; ++i) {if (p[i].l <= last) {continue;}ans++;last = p[i].r;}printf("%d\n", ans);}int main() {int counter = 1;while (scanf("%d%d", &n, &d), n || d) {printf("Case %d: ",counter++);init();work();}return 0;}