2004rc1.c

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

#define CMAX 20

typedef struct {
	int x;
	int y;
} PT;

double dist(PT a, PT b)
{
	return( sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) ) );
}

int main(void)
{
	int i,n;
	PT h,d,c[CMAX];
	int sumi[CMAX];
	double min,limit,nowdist;
	int last,count,next;
	
	while(1){
		scanf("%d %d %d %d %d",&n,&h.x,&h.y,&d.x,&d.y);
		if(n+h.x+h.y+d.x+h.y==0) break;
		
//		printf("\n%d (%d,%d) (%d,%d)\n",n,h.x,h.y,d.x,d.y);
		
		for(i=0; i<n; i++){
			scanf("%d %d", &c[i].x, &c[i].y);
//			printf("(%d,%d) ", c[i].x, c[i].y);
		}
//		printf("\n");
		
		
		for(i=0; i<n; i++){
			sumi[i]=0;
		}
		
		nowdist=0.0;
		for(count=0; count<n; count++){
			// 魔王から一番近いクリスタルを見つける
			min=9999.0;
			for(i=0; i<n; i++){
				if(sumi[i]) continue;
				if(dist(c[i],d)<min){
					min=dist(c[i],d);
					last=i;
				}
			}
			limit=min; // 魔王がここに来るまでに全て集めればよい
			printf("魔王から近いクリスタル (%d,%d) %f\n", c[last].x,c[last].y,limit);

			// 現在の位置から一番近いクリスタルを見つける
			min=9999.0;
			for(i=0; i<n; i++){
				if(sumi[i]) continue;
				if(dist(c[i],h)<min){
					min=dist(c[i],h);
					next=i;
				}
			}
			nowdist+=min;	// クリスタルまで移動して、距離を求める
			printf("[%d] 一番近いクリスタル (%d,%d) %f %f\n", count,c[next].x, c[next].y, min, nowdist);
			if(nowdist>=limit){	// リミットの距離を超えてしまったら全部集められない
				break;
			}
			sumi[next]=1;
			h=c[next];
		}
		if(count==n){
			puts("YES");
		}else{
			puts("NO");
		}
	}
	
	return(0);
}