Cod sursa(job #1846001)

Utilizator ASD135Radu M ASD135 Data 12 ianuarie 2017 00:42:57
Problema Adapost 2 Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <iostream>
#include <cmath>
using namespace std;

const int Q=50007;

int n;

struct point
{
	long double x,y;
}v[Q];

long double dist(long double a, long double b)
{
	long double rez=0;
	for(int i=1; i<=n; i++)
	{
		rez+=sqrt((a-v[i].x)*(a-v[i].x) + (b-v[i].y)*(b-v[i].y));
	}
	return rez;
}


int main()
{
	freopen("adapost2.in","r",stdin);
	freopen("adapost2.out","w",stdout);
	cin>>n;

	long double gx=0,gy=0;

	for(int i=1; i<=n; i++)
	{
		cin>>v[i].x>>v[i].y;
		gx+=v[i].x;
		gy+=v[i].y;
	}

	gx/=n;
	gy/=n;

	long double pas=1<<9;

	long double aux,dist_act=dist(gx,gy);

	for(int tmp=1; tmp<=30; tmp++)
	{
		aux=dist(gx,gy+pas);
		if(aux<dist_act)
		{
			gy+=pas;
			dist_act=aux;
			
		}
		aux=dist(gx+pas,gy);
		if(aux<dist_act)
		{
			gx+=pas;
			dist_act=aux;
		}
		aux=dist(gx-pas,gy);
		if(aux<dist_act)
		{
			gx-=pas;
			dist_act=aux;
			
		}
		aux=dist(gx,gy-pas);
		if(aux<dist_act)
		{
			gy-=pas;
			dist_act=aux;
		}
		pas/=2;
	}

	printf("%.6Lf %.6Lf\n",gx,gy);

	return 0;
}