#include<stdio.h>
#include<math.h>
#include<memory.h>
#include<stdlib.h>
struct Interal{
	double a;
	double b;
} in[1000];
bool en[1000];
int n,d;

int cmp(const void *a,const void *b)
{
	if((*(Interal *)a).a>(*(Interal *)b).a)
		return 1;
	else if((*(Interal *)a).a==(*(Interal *)b).a && (*(Interal *)a).b<(*(Interal *)b).b)
		return 1;
	else return -1;
}

void disp()
{
	for(int i=0;i<n;i++)
		printf("%lf %lf  ",in[i].a,in[i].b);
	printf("\n");
}

int find()
{
	qsort(in,n,sizeof(in[0]),cmp);
	//disp();
	memset(en,1,sizeof(en));
	for(int i=1;i<n;i++)
		if(in[i].b<=in[i-1].b)
			en[i-1]=false;

	double x=-1000000000;
	int cnt=0;
	for(int j=0;j<n;j++)
		if(en[j] && in[j].a>x){
			cnt++;
			x=in[j].b;
		}
	return cnt;
}

int main()
{
	int x,y;
	int t=0;
	while(1){
		scanf("%d%d",&n,&d);
		if(n==0 && d==0)
			break;

		t++;
		bool flag=true;	//can be solve or not
		double tmp;
		for(int i=0;i<n;i++){
			scanf("%d%d",&x,&y);
			if(y>d)
				flag=false;
			if(flag){
				tmp=sqrt((double)d*d-y*y);
				in[i].a=x-tmp;
				in[i].b=x+tmp;
			}
		}
		if(!flag)
			printf("Case %d: -1\n",t);
		else
			printf("Case %d: %d\n",t,find());
	}
	return 0;
}

• Re:我想知道我为啥错了，排序+贪心，我是把所有包含别的区间的区间都disable掉，再找，不好意思，贴代码求助 (49) BloodElf 2009-01-20 15:18:06