pku2627.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <math.h>
#define SIZE 1100

typedef struct 
{
	double x, y;
} Point;

typedef struct 
{
	int id;
	int dis;
} Node;

Node nd[SIZE];

Point p[SIZE];
int visited[SIZE];
double maxdis;
int N;

int Can(int i, int j)
{
	double di;
	di = (p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y);
	if (di <= maxdis)
	{
		return 1;
	}
	return 0;
}

int BFS()
{
	int head, tail, i;
	visited[0] = 1;
	nd[0].id = 0;
	nd[0].dis = 0;
	head = 0;
	tail = 1;

	while (head < tail)
	{
		for (i = 0; i < N; i++)
		{
			if (!visited[i] && Can(nd[head].id, i))
			{
				if (i == 1)
				{
					return nd[head].dis;
				}
				nd[tail].id = i;
				nd[tail].dis = nd[head].dis + 1;
				tail++;
				visited[i] = 1;
			}
		}
		head++;
	}
	return -1;
}

int main()
{
	int v, m, ans;
	scanf("%d %d", &v, &m);
	maxdis = v * m * 60;
	maxdis *= maxdis;
	N = 0;
	while (scanf("%lf %lf", &p[N].x, &p[N].y) != -1) N++;
	ans = BFS();
	if (ans == -1)
	{
		printf("No.\n");
	}
	else
	{
		printf("Yes, visiting %d other holes.\n", ans);
	}
	return 0;
}