Cod sursa(job #587070)

Utilizator ChallengeMurtaza Alexandru Challenge Data 3 mai 2011 20:23:53
Problema Adapost 2 Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>
#include <iomanip>
#include <cmath>

using namespace std;

const char InFile[]="adapost2.in";
const char OutFile[]="adapost2.out";
const int MaxN=50111;
const double EPS=1.0e-10;
const int DIR=4;
const double dx[]={0,0,1,-1};
const double dy[]={1,-1,0,0};

ifstream fin(InFile);
ofstream fout(OutFile);

int N;
double vx[MaxN],vy[MaxN],sx,sy;
double sol=1.0e64;

inline double dist(const double &x1, const double &y1, const double &x2, const double &y2)
{
	double dx=x1-x2;
	double dy=y1-y2;
	return sqrt(dx*dx+dy*dy);
}

inline double sumdist(const double x, const double y)
{
	double sum=0.0;
	for(register int i=1;i<=N;++i)
	{
		sum+=dist(vx[i],vy[i],x,y);
	}
	return sum;
}

int main()
{
	fin>>N;
	for(register int i=1;i<=N;++i)
	{
		fin>>vx[i];
		fin>>vy[i];
		sx+=vx[i];
		sy+=vy[i];
	}
	fin.close();

	sx/=(double)N;
	sy/=(double)N;
	sol=sumdist(sx,sy);
	for(double step=512.0;step>EPS;step*=0.5)
	{
		for(register int i=0;i<DIR;++i)
		{
			double d=sumdist(sx+dx[i]*step,sy+dy[i]*step);
			if(d<sol)
			{
				sol=d;
				sx+=dx[i]*step;
				sy+=dy[i]*step;

				step*=2.0;
				break;
			}
		}
	}

	fout<<setprecision(4)<<std::fixed;
	fout<<sx<<" "<<sy;
	fout.close();
	return 0;
}