#include <iostream>
#include <math.h>
#include <stdlib.h>

#define MX 1005

using namespace std;

double l[MX],r[MX];//左右交点
int num[MX];//索引数组

void mysort(int n)
{
	int i,j,p,tmp;
	double min;
	for (i=0; i<n-1; i++)
	{
		min=r[num[i]];
		p=i;
		for (j=i+1; j<n; j++)
		{
			if (min>r[num[j]])
			{
				min=r[num[j]];
				p=j;
			}
		}
		if (min<r[num[i]])
		{
			tmp=num[i];
			num[i]=num[p];
			num[p]=tmp;
		}
	}
}

inline bool change(double &a, double &b, double r)
{
	double tmp;
	if (b>r)
		return false;
	tmp=sqrt(r*r-b*b);
	b=tmp+a;
	a=-tmp+a;
	return true;
}

void main()
{
	int i,n,ks=1,radars;
	double d,now;
	while (cin>>n>>d && n)
	{
		radars=0;
		for (i=0; i<n; i++)
		{
			cin>>l[i]>>r[i];//由坐标计算过该点的圆在X轴上圆心的范围，便于贪心
			if (!change(l[i], r[i], d))
			{
				radars=-1;
				break;
			}
			num[i]=i;
		}
		if (radars!=-1)
		{
			mysort(n);//排序
			now=l[num[0]]-1;
			for (i=0; i<n; i++)
			{
				if (now<l[num[i]])
				{
					now=r[num[i]];
					radars++;
				}
			}
		}
		cout<<"Case "<<ks++<<": "<<radars<<endl;
	}
}

• Re:自己写了排序不RE了有WA，为什么啊？在ZJU就能过 (1301) guzhilei1986 2007-06-14 21:28:27