1052.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1052 on 2005-11-22 at 15:54:06 */ 
#include <cstdio>
#include <cstdlib>
#include <cmath>

const int MAX = 1024;
const double eps = 1e-4;
const double INFINITE = -5e6;

class Zone {
public:
	static int d;
	double x;
	double y;
	bool parse(int, int);
};
int Zone::d = 0;
bool Zone::parse(int ix, int iy) {
	if(iy > d) {
		return false;
	} else if(iy == d) {
		x = y = ix;
	} else {
		double r = sqrt(d*d - iy*iy);
		x = ix - r;
		y = ix + r;
	}
	return true;
}

int cmp(const void*, const void*);
inline double min(double, double);

int main()
{
	Zone zone[MAX];
	int n, x, y;
	int i, used, t = 0;
	bool can;
	double right;
	
	while(scanf("%d %d", &n, &Zone::d) == 2) {
		if(n == 0 && Zone::d == 0) {
			return 0;
		} else {
			can = true;
			used = 0;
			for(i = 0; i < n; i++) {
				scanf("%d %d", &x, &y);
				if(can) {
					can = zone[i].parse(x, y);
				}
			}
			t++;
			printf("Case %d: ", t);
			if(!can) {
				printf("-1\n");
			} else {
				right = INFINITE;
				qsort(zone, n, sizeof(Zone), cmp);
				for(i = 0; i < n; i++) {
					if(right - zone[i].x < -eps) {
						used++;
						right = zone[i].y;
					} else {
						right = min(right, zone[i].y);
					}
				}
				printf("%d\n", used);
			}
		}
	}
	
	return 0;
}

int cmp(const void *a, const void *b)
{
	Zone *x = (Zone*)a, *y = (Zone*)b;
	
	if(x->x - y->x < -eps) {
		return -1;
	} else if(x->x - y->x > eps) {
		return 1;
	} else if(x->y - y->y < eps) {
		return -1;
	} else {
		return 1;
	}
}
inline double min(double x, double y)
{
	if(x - y < eps) {
		return x;
	} else {
		return y;
	}
}