Cod sursa(job #597910)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 23 iunie 2011 22:43:38
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<stdio.h>
#include<math.h>

#define maxN 50005
#define eps 1e-4

FILE*f=fopen("adapost2.in","r");
FILE*g=fopen("adapost2.out","w");

int n,i,d; double step,x,y,distmin,aux;
int di[4] = {0,0,-1,1};
int dj[4] = {-1,1,0,0};

struct pct{
	double x;
	double y;
}A[maxN];
	
inline double sumdist ( double x, double y ){
	double dist = 0;
	
	for ( i = 1 ; i <= n ; ++i ){
		dist += sqrt( (x - A[i].x) * (x - A[i].x) + (y - A[i].y) * (y - A[i].y) );
	}
	return dist;
}

inline void citire () {
	
	fscanf(f,"%d",&n);
	
	for ( i = 1 ; i <= n ; ++i ){
		fscanf(f,"%lf %lf",&A[i].x,&A[i].y);
		x += A[i].x; y += A[i].y;
	}
	
	x /= n; y /= n;
}

inline void solve () {
	
	distmin = sumdist(x,y);
	
	for ( step = 512.0 ; step >= eps ; step /= 2 ){
		for ( d = 0 ; d < 4 ; ++d ){
			if ( (aux = sumdist(x+di[d]*step,y+dj[d]*step) ) < distmin ){
				distmin = aux;
				x += di[d] * step; y += dj[d]*step;
				step *= 2;
				break;
			}
		}
	}
	
	fprintf(g,"%lf %lf\n",x,y);
}

int main () {
	
	citire();
	solve();
	
	fclose(f);
	fclose(g);
	
	return 0;
}