POJ 1328

1328.cpp

#include <cstdio>
#include <cmath>
#include <utility>
#include <algorithm>
using namespace std;

#define EPS (1e-6)
typedef pair<long double, long double> Coor;
typedef pair<long double, Coor> Pair;

int n;
long double d;
Pair order[1000];
bool impossible;

inline bool is_involved(Coor p, long double pos) {
    return (p.first-pos)*(p.first-pos) + p.second*p.second <= d*d + EPS;
}

int main() {
    int count = 0;

    while (1) {
        int ans;
        int _d;

        scanf("%d %d", &n, &_d);
        if (n == 0 && _d == 0) return 0;
        d = (long double)_d;

        count++;
        impossible = false;
        for (int i=0; i<n; i++) {
            int _x, _y;
            long double x, y;
            long double square;
            long double root;
            long double center;
    
            scanf("%d %d", &_x, &_y);
            x = (long double)_x;
            y = (long double)_y;
            square = d*d - y*y;
            if (square < -EPS) {
                impossible = true;
                continue;
            }
            root = sqrt(square);
            order[i] = Pair(x+root, Coor(x, y));
        }

        if (impossible) {
            printf("Case %d: -1\n", count);
            continue;
        }

        sort(order, order+n);
        ans = 0;
        for (int i=0; i<n;) {
            long double pos = order[i++].first;

            ans++;
            for (; i<n; i++) {
                if (!is_involved(order[i].second, pos)) break;
            }
        }

        printf("Case %d: %d\n", count, ans);
    }
}