pku2253.cpp

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

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

typedef struct
{
	int dis;
	int owner[2];	
} Dis;

Dis d[40000];
int n;
int point[200][2];
int status[200];

int cmp(const void *a, const void *b)
{
	Dis *ap = (Dis *)a;
	Dis *bp = (Dis *)b;
	return ap->dis - bp->dis;
}

double calc()
{
	int i, j, k;
	
	for (i = 0; i < n; i++)
	{
		status[i] = i;	
	}
	
	for (i = 0, j = 0; j < n - 1; j++)
	{
		for (k = j + 1; k < n; k++)
		{
			d[i].dis = (point[j][0] - point[k][0]) * (point[j][0] - point[k][0]) 
				+  (point[j][1] - point[k][1]) * (point[j][1] - point[k][1]);
			d[i].owner[0] = j;
			d[i].owner[1] = k;
			i++;
		}	
	}
	
	qsort(d, (n - 1) * n / 2, sizeof(d[0]), cmp);
	
	for (i = 0; 1 ; i++)
	{
		int pa = status[d[i].owner[0]];
		int pb = status[d[i].owner[1]];
		
		if (pa != pb)
		{
			for (j = 0; j < n; j++)
			{
				if (status[j] == pb)
				{
					status[j] = pa;	
				}	
			}
		}
		if (status[1] == status[0])
		{
			break;	
		}
	}
	return sqrt(d[i].dis);	
}


int main()
{
	int i, t;
	t = 0;
	while (scanf("%d", &n) != -1 && n!=0)
	{
		for (i = 0; i < n; i++)
		{
			scanf("%d %d", &point[i][0], &point[i][1]);	
		}
		t++;
		printf("Scenario #%d\nFrog Distance = %.3lf\n\n", t, calc());
	}
	
	return 0;
}