Cod sursa(job #1845994)

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

const int Q=50007;

int n;

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

double dist(double a, double b)
{
	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;

	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;

	double pas=1<<9;

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

	for(int tmp=1; tmp<=100; 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;
}