Cod sursa(job #37215)

Utilizator amadaeusLucian Boca amadaeus Data 24 martie 2007 18:11:33
Problema Adapost 2 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <cstdio>
#include <cmath>

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

#define EPS 0.0001
#define STEP 0.9

using namespace std;

struct point {
	double x, y;
};

int N;
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;
	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 = 100; temp > EPS; temp *= STEP ) {
		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;
		}
	}
}

void scr() {
//	printf( "%.4lf %.4lf - %.5lf\n", P.x, P.y, 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;
}