Cod sursa(job #587047)

Utilizator ChallengeMurtaza Alexandru Challenge Data 3 mai 2011 20:08:34
Problema Adapost 2 Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 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-6;
const int DIR=4;
const double dx[]={0,0,1,-1};
const double dy[]={1,-1,0,0};

struct s_point
{
	s_point(double _x=0.0, double _y=0.0):x(_x),y(_y){}
	double x,y;

	double dist(const s_point &a) const
	{
		double dx(x-a.x),dy(y-a.y);
		return sqrt(dx*dx+dy*dy);
	}
};

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

int N;
s_point v[MaxN],G,solpoint;
double sol=1.0e64;

inline double sumdist(const s_point &P)
{
	double sum=0.0;
	for(register int i=1;i<=N;++i)
	{
		sum+=P.dist(v[i]);
	}
	return sum;
}

int main()
{
	fin>>N;
	for(register int i=1;i<=N;++i)
	{
		fin>>v[i].x;
		fin>>v[i].y;
		G.x+=v[i].x;
		G.y+=v[i].y;
	}
	fin.close();

	G.x/=(double)N;
	G.y/=(double)N;
	solpoint=G;
	sol=sumdist(solpoint);
	for(double step=512.0;step>EPS;step*=0.5)
	{
		for(register int i=0;i<DIR;++i)
		{
			double d=sumdist(s_point(solpoint.x+dx[i]*step,solpoint.y+dy[i]*step));
			if(d<sol)
			{
				sol=d;
				solpoint.x+=dx[i]*step;
				solpoint.y+=dy[i]*step;

				step*=2.0;
				break;
			}
		}
	}

	fout<<setprecision(4)<<std::fixed;
	fout<<solpoint.x<<" "<<solpoint.y;
	fout.close();
	return 0;
}