pku2728.cpp

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

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

typedef struct 
{
	int x, y, h;
} Point;

typedef struct 
{
	int id;
	double val;
} Edge;

Point p[1001];
double r;
int N;

int abs(int x)
{
	return x > 0 ? x : -x;
}
double Dis(int i, int j)
{
	return sqrt((p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y));
}

int Cost(int i, int j)
{
	return abs(p[i].h - p[j].h);
}

double Value(int i, int j)
{
	return Cost(i, j) - Dis(i, j) * r;
}

double Prim()
{
	double min;
	int u[1001];
	int i, j, k, minid;
	int Tcost;
	double Tlength;
	double Tsum;
	Edge mindis[1001];
	
	for (i = 1; i < N; i++)
	{
		mindis[i].val = Value(0, i);
		mindis[i].id = 0;
		u[i] = 0;
	}
	u[0] = 1;
	Tcost = 0;
	Tlength = 0;
	Tsum = 0;

	for (k = 1; k < N; k++)
	{
		min = 1e30;

		for (i = 0; i < N; i++)
		{
			if (u[i] == 1)
			{
				continue;
			}
			if (mindis[i].val < min)
			{
				minid = i;
				min = mindis[i].val;
			}
		}
		u[minid] = 1;

		Tcost += Cost(minid, mindis[minid].id);
		Tlength += Dis(minid, mindis[minid].id);
		Tsum += min;

		for (i = 0; i < N; i++)
		{
			if (u[i])
			{
				continue;
			}
			if (mindis[i].val > Value(i, minid))
			{
				mindis[i].val = Value(i, minid);
				mindis[i].id = minid;
			}
		}
	}
	return Tcost / Tlength;
}

int main()
{
	int i;
	double r2;

	while (scanf("%d", &N) != -1 && N > 0)
	{
		for (i = 0; i < N; i++)
		{
			scanf("%d %d %d", &p[i].x, &p[i].y, &p[i].h);
		}
		r2 = 0;
		do
		{
			r = r2;
			r2 = Prim();
		}
		while (fabs(r - r2) > 5e-4);
		printf("%.3lf\n", r);
	}
	return 0;
}