Cod sursa(job #11829)

Utilizator Binary_FireFlorin Pogocsan Binary_Fire Data 1 februarie 2007 21:16:51
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<math.h>
#include<stdio.h>
#define fin  "adapost2.in"
#define fout "adapost2.out"
#define Nmax 50001
double v[Nmax][2],field,x,y,best;
int n;
FILE *in,*out;

double distance(double x1,double y1,double x2,double y2) {
double a,b;
	a=x1-x2;
	b=y1-y2;
	return sqrt(a*a+b*b);
}

int test(double x,double y) {
double tot;
int i;
	tot=0.0;
	for (i=1;i<=n;++i) 
		tot+=distance(v[i][0],v[i][1],x,y);
	
	if (tot<best) {
		best=tot; return 1;
	}

	return 0;
}

void search() {

	if (test(x-field,y)) { 
		x-=field;
		search();
		return ;
	}

	if (test(x,y-field)) {
		y-=field;
		search();
		return ;
	}
	
	if (test(x+field,y)) { 
		x+=field;
		search();
		return ;
	}

	if (test(x,y+field)) {
		y+=field;
		search();
		return ;
	}
	
	//printf("%lf %lf\n",x,y);

	field/=10.0;

	if (field<0.0001) return ;
	
	else search();

}

int main() {
int i,j;
	in=fopen(fin,"r"); out=fopen(fout,"w");
	
	fscanf(in,"%i",&n);	
	
	for (i=1;i<=n;++i) fscanf(in,"%lf%lf",&v[i][0],&v[i][1]);
	
	best=100000000000000.0;

	field=100.0;

	//printf("%lf\n",best);

	search();

	fprintf(out,"%lf %lf\n",x,y);

	return 0;
}