Cod sursa(job #67070)

Utilizator megabyteBarsan Paul megabyte Data 22 iunie 2007 14:28:46
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <cstdio>
#include <cmath>
#include <iostream>
#define INF  "adapost2.in"
#define OUF  "adapost2.out"
#define NMAX 50002
#define EPS  1e-4
using namespace std;

int n;

inline double dab(double x2,double x1,double y2,double y1)
{
	double d1,d2;
	d1=x2-x1;d1*=d1;
	d2=y2-y1;d2*=d2;
	return sqrt((d1+d2));
}

inline double sumd(double x[],double y[],double ox,double oy)
{
	register int i;
	double sum=0.0;
	for(i=1;i<=n;++i) sum+=dab(x[i],ox,y[i],oy);
	return sum;
}

int main()
{
	FILE *in,*out;
	double x[NMAX],y[NMAX],sx,sy,sum,ax,ay,asum;
	double dy[4]={128,0,-128,0},dx[4]={0,128,0,-128};
	int i,ok,k;
	in=fopen(INF,"r");
	out=fopen(OUF,"w");
	fscanf(in,"%d",&n);
	for(i=1;i<=n;++i) fscanf(in,"%lf%lf",&x[i],&y[i]);
	sx=0.0;sy=0.0;
	for(i=1;i<=n;++i) 
	{
		sx+=x[i];
		sy+=y[i];
	}
	sx/=n; sy/=n;
	sum=sumd(x,y,sx,sy);

	while(dy[0]>EPS)
	{
		ok=0;
		for(k=0;k<4&&!ok;++k)
		{
			ax=sx+dx[k];
			ay=sy+dy[k];
			asum=sumd(x,y,ax,ay);
			if(asum<sum) ok=1;
		}
		
		if(ok)
		{
			sx=ax;sy=ay;
			sum=asum;
		}
		else
			for(k=0;k<4;++k) { dy[k]/=2;dx[k]/=2; }
	}

	fprintf(out,"%lf %lf\n",sx,sy);
	fclose(in);fclose(out);
	return 0;
}