Cod sursa(job #1046576)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 3 decembrie 2013 09:49:00
Problema Adapost 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<cstdio>
#include<cmath>
#define dim 50006
using namespace std;


double x,y,Dabs,step;
int i,n;
struct {
double x,y;
}v[dim];
double Dist(double x,double y){
	double s=0.0;
	for(int i=1;i<=n;++i){
		s+=sqrt((x-v[i].x)*(x-v[i].x)+(y-v[i].y)*(y-v[i].y));
	}
	return s;
}
int main () {
	
	freopen("adapost2.in","r",stdin);
    freopen("adapost2.out","w",stdout);
	
	
	scanf("%d",&n);
	
	for(i=1;i<=n;++i) {
		scanf("%lf%lf",&v[i].x,&v[i].y);
		x+=v[i].x;
		y+=v[i].y;
	}
	x/=n;
	y/=n;
	step=200;
	Dabs=Dist(x,y);
	
	while(step>0.0001) {
		
		double dx[]={step,-step, 0, 0};
        double dy[]={0, 0, step,-step};
		bool ok=1;
		double xa=0;
		double ya=0;
		double D=Dabs;
		for(i=0;i<=3;++i){
			if(Dist(x+dx[i],y+dy[i])<D){
				D=Dist(x+dx[i],y+dy[i]);
				xa=x+dx[i];
				ya=y+dy[i];
				ok=0;
			}
		}
		if(ok==0) {
			Dabs=D;
			x=xa;
			y=ya;
		}
		step/=2;
	}
	
	printf("%lf %lf\n",x,y);
	return 0;
}