Cod sursa(job #37242)

Utilizator amadaeusLucian Boca amadaeus Data 24 martie 2007 18:32:17
Problema Adapost 2 Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <cstdio>
#include <cmath>

#define NX 50001
#define sqr(x) ( (x) * (x) )

#define EPS 0.00001
#define STEP 0.666

using namespace std;

struct point {
	double x, y;
};

int N, cnt;
point v[ NX ], CG, P, PP;
double E, EE;

void cit() {
	scanf( "%d", &N );
	for( int i = 1; i <= N; i++ ) {
		scanf( "%lf%lf", &v[i].x, &v[i].y );
		CG.x += v[i].x / N;
		CG.y += v[i].y / N;
	}
}

double dist( point P ) {
	double res = 0;
	cnt++;
	for( int i = 1; i <= N; i++ )
		res += sqrt( sqr( P.x - v[i].x ) + sqr( P.y - v[i].y ) );
	return res;
}

void rez() {
	double temp;
	
	P = CG; E = dist( P );

	for( temp = 50; temp > EPS; ) {
		PP.x = P.x; PP.y = P.y + temp; EE = dist( PP );
		if( EE < E ) {
			P = PP; E = EE; continue;
		}
		PP.x = P.x; PP.y = P.y - temp; EE = dist( PP );
		if( EE < E ) {
			P = PP; E = EE; continue;
		}
		PP.x = P.x + temp; PP.y = P.y; EE = dist( PP );
		if( EE < E ) {
			P = PP; E = EE; continue;
		}
		PP.x = P.x - temp; PP.y = P.y; EE = dist( PP );
		if( EE < E ) {
			P = PP; E = EE; continue;
		}
		temp *= STEP;
	}
}

void scr() {
//	printf( "%.4lf %.4lf\n%d %.7lf\n", P.x, P.y, cnt, dist( P ) );
	printf( "%.4lf %.4lf\n", P.x, P.y );
}

int main() {
	freopen( "adapost2.in", "r", stdin );
	freopen( "adapost2.out", "w", stdout );

	cit();
	rez();
	scr();

	return 0;
}