#include<stdio.h>
#include"stdlib.h"
#include<math.h>
int n,d,sign;
struct arix//记录左右区间
{
	double a;
	double b;
}arixs[1050];
int cmp(struct arix *x,struct arix *y)//对左右区间进行排序，先按右区间从小到大，右区间相等按左区间排
{
	if(x->b!=y->b) return x->b-y->b;
	else return x->a-y->a;
}
void read_input()
{
	int i,x,y;
	double tem;
	sign=0;
	for(i=0;i<n;i++)
		{
			scanf("%d%d",&x,&y);
			tem=sqrt((double)(d)*d-(double)(y)*y);
			arixs[i].a=x-tem;
			arixs[i].b=x+tem;
			if(d<y)sign=-1;
	}
	if(sign==-1)return 0;
}
int solve()
{
	int i,flag=0,point=-1;
	if(sign==-1)return 0;
	for(i=1;i<n;i++)//非常简单的贪心
	{
		if(arixs[i].a>arixs[flag].b){point++;flag=i;}//记录上一个取右短点的区间
	}
	return point;
}
int main()
{
	int point,time=1;
	while(scanf("%d%d",&n,&d)&&(n||d))
	{
		read_input();
		if(sign==-1) printf("Case %d: %d\n",time++,sign);
		else {
		qsort(arixs,n,sizeof(arixs[0]),cmp);
		printf("Case %d: ",time++);
		point=solve();
		printf("%d\n",point+2);
		}
	}
	system("pause");
	return 0;
}

• Re:思路很清晰，一直WA，是精度的原因还是啥？ 找到的测试用例全过了，帮忙看看吧，谢谢啦~ (177) liaolong 2011-04-16 14:38:51
  • Re:思路很清晰，一直WA，是精度的原因还是啥？ 找到的测试用例全过了，帮忙看看吧，谢谢啦~ (37) illuminator 2013-03-18 14:46:37
• Re:思路很清晰，一直WA，是精度的原因还是啥？ 找到的测试用例全过了，帮忙看看吧，谢谢啦~ (1129) qijinbiao 2011-07-20 20:54:26