Cod sursa(job #11903)

Utilizator blasterzMircea Dima blasterz Data 2 februarie 2007 11:55:52
Problema Adapost 2 Scor 9
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <cstdio>
#define maxn 50001
#include <cmath>
#define next(p) (((p)*10+1)/(double)10)
struct point { double x, y;};
point x[maxn];

	double meda=1000, medb=1000, solx, soly;
	double smin=0x3f3f3f3f;
	
double distance(point a, point b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int n;

double oki(point a)
{
	double sum=0;
	for(int i=1;i<=n;i++) sum+=distance(a, x[i]);
	
	return sum;
}


void recursion(double mx, double my, double newx, double newy)
{
	point m;
	m.x=mx+newx;
	m.y=my+newy;
	double sum=oki(m);
		if(smin-sum>=0.0001) {  smin=sum;solx=m.x; soly=m.y; recursion(m.x, m.y, newx/2.0, newy/2.0);}
		
	m.x=mx-newx;
	m.y=my+newy;
	sum=oki(m);
		if(smin-sum>=0.0001) {  smin=sum;solx=m.x; soly=m.y; recursion(m.x, m.y, newx/2.0, newy/2.0);}

	m.x=mx+newx;
	m.y=my-newy;
	
	sum=oki(m);
		if(smin-sum>=0.0001) {  smin=sum;solx=m.x; soly=m.y; recursion(m.x, m.y, newx/2.0, newy/2.0);}
		
	m.x=mx-newx;
	m.y=my-newy;
	
	sum=oki(m);
		if(smin-sum>=0.0001) {  smin=sum;solx=m.x; soly=m.y; recursion(m.x, m.y, newx/2.0, newy/2.0);}
}
		
int main()
{
	int i;
	freopen("adapost2.in", "r",stdin);
	scanf("%d\n", &n);
	for(i=1;i<=n;i++) scanf("%lf %lf\n", &x[i].x, &x[i].y);
	
	
	//printf("%f\n", x[1].x);
	double medx=0, medy=0;
	for(i=1;i<=n;i++) medx+=x[i].x, medy+=x[i].y;
	medx=medx/(double) n;
	medy=medy/(double) n;
	freopen("adapost2.out", "w", stdout);
	//printf("%lf %lf\n", medx, medy);
/*
	int ok=1;
	while(ok)
	{
		ok=0;
		point m;
		m.x=medx+meda;
		m.y=medy+medb;
		
		double sum=oki(m);
		if(smin-sum>=0.00001) { ok=1; smin=sum;solx=m.x; soly=m.y;}
		m.x=medx+meda;
		m.y=medy-medb;
		
		sum=oki(m);
		if(smin-sum>=0.00001) { ok=1; smin=sum; solx=m.x; soly=m.y;}
		
		m.x=medx-meda;
		m.y=medy+medb;
		
		sum=oki(m);
		if(smin-sum>=0.00001) { ok=1; smin=sum; solx=m.x; soly=m.y;}
		
		m.x=medx-meda;
		m.y=medy+medb;
		
		if(smin-sum>=0.00001) { ok=1; smin=sum; solx=m.x; soly=m.y;}
		
		meda=meda/2.0;
		medb=medb/2.0;
	//	printf("%lf %lf\n", meda, medb);
	}
	*/	
	recursion(medx, medy, 100.0, 100.0);
	printf("%lf %lf\n", solx, soly);
	
	return 0;
}