2728.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:2728  User Id:fzk 
Memory:7932K  Time:218MS
Language:G++  Result:Accepted

Source 

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

using namespace std;

int h[1000], x[1000], y[1000], n;
double dis[1000][1000];

void clac_dis() {
	int i, j;
	for( i=0; i<n; i++ )
	for( j=i+1; j<n; j++ )
		dis[j][i] = dis[i][j] = sqrt( (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]) );
}

double r;

inline double value( int i, int j ) {
	return abs(h[i]-h[j])-dis[i][j]*r;
}

int f[1000];
double s[1000];
bool sign[1000];

void Prim( ) {
	int i, j, k;
	double t;

	memset( sign, 0, sizeof sign );

	for( i=0; i<n; i++ )
		s[i] = 1e100;
	s[0] = 0;
	f[0] = -1;

	for( i=0; i<n; i++ ) {
		k = -1;
		for( j=0; j<n; j++ )
			if( !sign[j] && ( k<0 || s[k] > s[j] ) )
				k = j;
		
		sign[k] = true;

		for( j=0; j<n; j++ )
			if( !sign[j] && s[j] > (t=value( k, j )) ) {
				s[j] = t;
				f[j] = k;
			}
	}
}

double clac_r( ) {
	double s1=0, s2=0;
	int i;
	
	for( i=0; i<n; i++ )
		if( f[i]>=0 ) {
			s1 += abs( h[i] - h[f[i]] );
			s2 += dis[i][f[i]];
		}

	return s1/s2;
}

double greed() {
	int i, j, k;
	double s1 = 0, s2 = 0, best;
	for( i=0; i<n; i++ ) {
		k = i+1;
		best = fabs( h[i]-h[i+1] ) / dis[i][i+1];
		for( j=i+2; j<n; j++ )
			if( fabs(h[i]-h[j]) / dis[i][j] < best ) {
				best = fabs(h[i]-h[j]) / dis[i][j];
				k = j;
			}

		s1 += fabs(h[i]-h[k] );
		s2 += dis[i][k];
	}
	return s1/s2;
}

int main( ){
	int i;
	double t;
	while( scanf( "%d", &n ) == 1 && n > 0 ) {
		for( i=0; i<n; i++ )
			scanf( "%d%d%d", &x[i], &y[i], &h[i] );
		clac_dis( );
		r = greed();
		t = 0;
		while( fabs(t-r)>1e-4 ) {
			Prim();
			t = r;
			r = clac_r();
		}
		printf( "%.3lf\n", r );
	}

	return 0;
}