Cod sursa(job #1053507)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 12 decembrie 2013 20:00:18
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.05 kb
#include<fstream>
#include<cstdio>
#include<cmath>
#define EPS 0.0001
using namespace std;
int n;
struct Punct{double x,y;};
Punct P[50100],sol;
double dx[]={1.0,0.0,-1.0,0.0};
double dy[]={0.0,1.0,0.0,-1.0};
double distsol;

inline double Dist(Punct A)
{
	double rez=0.0;
	for(int i=1;i<=n;i++)
		rez+=sqrt((A.x-P[i].x)*(A.x-P[i].x)+(A.y-P[i].y)*(A.y-P[i].y));
	return rez;
}

int main()
{
	int i;
	double step,distnow;
	Punct now;
	bool changed;
	ifstream fin("adapost2.in");
	fin>>n;
	for(i=1;i<=n;i++)
	{
		fin>>P[i].x>>P[i].y;
		sol.x+=P[i].x;
		sol.y+=P[i].y;
	}
	fin.close();
	
	sol.x/=(1.0*n);
	sol.y/=(1.0*n);
	distsol=Dist(sol);
	for(step=8.0;step>EPS;step/=2.0)
	{
		changed=false;
		for(i=0;i<4 && !changed;i++)
		{
			now.x=sol.x+step*dx[i];
			now.y=sol.y+step*dy[i];
			distnow=Dist(now);
			if(distnow<distsol)
			{
				distsol=distnow;
				sol=now;
				changed=true;
			}
		}
		if(changed)
			step*=2.0;
	}
	
	freopen("adapost2.out","w",stdout);
	printf("%.5lf %.5lf\n",sol.x,sol.y);
	return 0;
}