2420.txt

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

#include "stdio.h"
#include "math.h"

double x[100], y[100];
int n;
const double eps = 1e-3;

double clac( double ox, double oy ) {
	int i;
	double s = 0;
	for( i=0; i<n; i++ )
		s += sqrt( (x[i]-ox)*(x[i]-ox) + (y[i]-oy)*(y[i]-oy) ); 
	return s;
}


void doit( ) {
	int i;
	double ox = 0, oy = 0, s0, s1, s2, s3, s4;
	double ddx = 1, ddy = 1;

	for( i=0; i<n; i++ )
		ox += x[i], oy += y[i];
	ox = oy = 0;
//	ox /= n, oy /= n;

	while(  fabs(ddx) + fabs(ddy) > eps ) {
		s0 = clac( ox, oy );
		s1 = clac( ox+eps, oy );
		s2 = clac( ox+eps*2, oy );
		s3 = clac( ox, oy+eps );
		s4 = clac( ox, oy+eps*2 );

		ox -= ( ddx = (s1-s0) ) / ( (s2-s1)/eps - (s1-s0)/eps );
		oy -= ( ddy = (s3-s0) ) / ( (s4-s3)/eps - (s3-s0)/eps );
	}

	printf( "%.0lf\n", clac( ox, oy ) );
}

int main( ) {
	int i;
	scanf( "%d", &n );
	for( i=0; i<n; i++ )
		scanf( "%lf%lf", x+i, y+i );
	doit( );
	return 0;
}