2092.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2092 on 2005-10-06 at 09:18:22 */ 
#include <cstdio>
#include <cstring>
#include <cmath>
#define  MAX  1024
#define  LIMIT  100000
#define  MIN  1e-10

typedef struct {
	double x;
	double y;
} Hole;

double distance(Hole*, Hole*);

int main()
{
	int v, m, n, d[MAX], min;
	int i, j, h;
	bool S[MAX], prey;
	Hole hole[MAX];
	double dis, limitd;
	char s[256];
	
	while(scanf("%d %d", &v, &m) == 2) {
		limitd = (double)v * m * 60;
		while(getchar() != '\n')
			;
		for(n = 0; ; n++) {
			gets(s);
			if(strchr(s, '*') == NULL) {
				sscanf(s, "%lf %lf", &hole[n].x, &hole[n].y);
			} else {
				break;
			}
		}
		for(i = 0; i < n; i++) {
			S[i] = false;
			d[i] = MAX;
		}
		d[0] = 0;
		prey = false;
		for(i = 0; i < n; i++) {
			min = MAX;
			h = -1;
			for(j = 0; j < n; j++) {
				if(!S[j] && min > d[j]) {
					min = d[j];
					h = j;
				}
			}
			if(h == -1) {
				prey = true;
				break;
			} else {
				S[h] = true;
			}
			for(j = 0; j < n; j++) {
				if(!S[j]) {
					dis = distance(&hole[h], &hole[j]);
					if(dis - limitd < MIN && d[j] > d[h]+1) {
						d[j] = d[h]+1;
					}
				}
			}
			if(d[1] != MAX) {
				break;
			}
		}
		if(!prey) {
			printf("Yes, visiting %d other holes.\n", d[1]-1);
		} else {
			printf("No.\n");
		}
	}
	
	return 0;
}

double distance(Hole *a, Hole *b)
{
	double d;

	d = sqrt((a->x - b->x)*(a->x - b->x) + (a->y - b->y)*(a->y - b->y));
	return d;
}