#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

typedef struct INTERVAL
{
	double l, r;
}INTERVAL;
INTERVAL p[1000];

int cmp(const void* p1, const void* p2)
{
	double x = ((INTERVAL*)p1)->l, y = ((INTERVAL*)p2)->l;
	if(x >= y)	return 1;
	else	return -1;
}

int main()
{
	int n, d, i, x[1000], y[1000], flag = 0, t = 0, num;
	double tmp, right;
	while(scanf("%d%d", &n, &d) && !(n == 0 && d == 0))
	{
		t++;
		if(d <= 0)
		{
			printf("Case %d: %d\n", t, -1);
			continue;
		}
		for(i = 0; i < n; i++)
		{
			scanf("%d%d", x + i, y + i);
			if(y[i] > d)
			{
				flag = 1;
				printf("Case %d: %d\n", t, -1);
				break;
			}
			tmp = sqrt(d * d - y[i] * y[i]);
			p[i].l = x[i] - tmp;
			p[i].r = x[i] + tmp;
		}
		if(flag)	continue;
		qsort(p, n, sizeof(INTERVAL), cmp);
		right = p[0].r;
		num = 1;
		for(i = 1; i < n; i++)
		{
			if(right < p[i].l)
				num++, right = p[i].r;
			else if(p[i].r < right)
				right = p[i].r;
		}
		printf("Case %d: %d\n", t, num);
	}
	return 0;
}

• Re:哪里错了 wa疯了 (1051) ziqilau 2008-09-03 17:18:26
  • 终于过了 (3) ziqilau 2008-09-03 17:27:06