pku2349.cpp

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

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define TheMax 100000000

int S, P;
int st[500];
int dis[500];
int p[500][2];
int mindis[500];

int cmp(const void *a, const void *b)
{
	return *(int *)b - *(int *)a;
}

int d(int i, int j)
{
	return (p[i][0] - p[j][0]) * (p[i][0] - p[j][0]) + (p[i][1] - p[j][1]) * (p[i][1] - p[j][1]);
}

double calc()
{
	int i, j, k, u, max, tmp;
	
	for (i = 1; i < P; i++)
	{
		mindis[i] = d(0, i);
	}
	
	for (i = 0; i < P; i++)
	{
		st[i] = 0;
	}

	st[0] = 1;

	for (i = 0; i < P - 1; i++)
	{
		max = TheMax;
		for (j = 0; j < P; j++)
		{
			if (st[j] == 0 && mindis[j] < max)
			{
				max = mindis[j];
				u = j;
			}
		}
	
		dis[i] = max;

		st[u] = 1;

		for (j = 0; j < P; j++)
		{
			if (st[j] == 0)
			{
				tmp = d(j, u);
				if (tmp < mindis[j])
				{
					mindis[j] = tmp;
				}
			}
		}
	}
	qsort(dis, P - 1, sizeof(dis[0]), cmp);
	printf("%.2lf\n", sqrt(dis[S - 1]));
}


int main()
{
	int t, i, j;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d%d", &S, &P);
		for (i = 0; i < P; i++)
		{
			scanf("%d%d", &p[i][0], &p[i][1]);
		}
		calc();
	}
	return 0;
}