本题在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; }