Cod sursa(job #12102)

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

	double meda=997, medb=997, solx, soly;
	double smin=0x3f3f3f3f;
	
double distance(point a, point b)
{
	return (double)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 (double)sum;
}


void recursion(double mx, double my,double newx,double newy)
{
	point m;
	m.x=mx+newx;
	m.y=my+newy;
	int ok=1;
  double sum=oki(m);
	if(smin-sum>=ep) {ok=0;  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>=ep) {  ok=0;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>=ep) { ok=0; 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>=ep) {  ok=0;smin=sum;solx=m.x; soly=m.y; recursion(m.x, m.y, newx/2.0, newy/2.0);}
	if(newx-ep>0 && ok) recursion(mx, my, 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);
	point aux;
	aux.x=medx;
	aux.y=medy;
	meda=997.0;
	medb=997.0;
	smin=oki(aux);
	//printf("%lf\n", smin);
	solx=medx;
	soly=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>=ep) { ok=1; smin=sum;solx=m.x; soly=m.y;}
		m.x=medx+meda;
		m.y=medy-medb;
		//printf("(%lf)\n", sum);
		sum=oki(m);
		if(smin-sum>=ep) { ok=1; smin=sum; solx=m.x; soly=m.y;}
		
		m.x=medx-meda;
		m.y=medy+medb;
		//printf("(%lf)\n", sum);
		sum=oki(m);
		if(smin-sum>=ep) { ok=1; smin=sum; solx=m.x; soly=m.y;}
		
		m.x=medx-meda;
		m.y=medy+medb;
		//printf("(%lf)\n", sum);
		if(smin-sum>=ep) { ok=1; smin=sum; solx=m.x; soly=m.y;}
		medx=solx;
		medy=soly;
		//printf("(%lf)\n", sum);
		if(ok==0 && meda-ep >0) ok=1;
		meda=meda/2.0;
		medb=medb/2.0;
	//	printf("%lf %lf\n", meda, medb);
	}
		
	recursion(medx, medy, 997.0, 997.0);
	printf("%lf %lf\n", solx, soly);
	//printf("%lf\n", smin);
	point ap;
	ap.x=4.1442; ap.y=4.2898;
	//printf("%lf\n", oki(ap));
	
	return 0;
}