Cod sursa(job #1815713)

Utilizator aaether14Dinescu Stefan Cristian aaether14 Data 25 noiembrie 2016 18:09:52
Problema Adapost 2 Scor 92
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <algorithm>


struct punct
{
	double x,y;
};



int n;
punct adapost_final, adapost_curent, soldati[50001];
double best_distance;
double current_distance;


const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};



double cost(punct p)
{
	double cost = 0;
	for (int i = 0; i < n; ++i)
		cost += std::sqrt((soldati[i].x - p.x) * (soldati[i].x - p.x) + (soldati[i].y - p.y) * (soldati[i].y - p.y)); 
	return cost;
}


int main()
{


	std::ifstream fin("adapost2.in");
	std::ofstream fout("adapost2.out");


	fin>>n;
	for (int i = 0; i < n; ++i)
	{
		fin>>soldati[i].x>>soldati[i].y;
		adapost_final.x += soldati[i].x;
		adapost_final.y += soldati[i].y;
	}
	adapost_final.x/=n;
	adapost_final.y/=n;


	best_distance = cost(adapost_final);
	double pas = 500.0;
	while (pas > 0.0000001)
	{
		for (int i = 0; i < 4; ++i)
		{
			adapost_curent = {adapost_final.x + dx[i] * pas, adapost_final.y + dy[i] * pas};
			current_distance = cost(adapost_curent);
			if (current_distance < best_distance)
			{
				best_distance = current_distance;
				adapost_final = adapost_curent;
			}
		}
		pas /= 2.0;
	}


	fout << adapost_final.x << " " << adapost_final.y;
	fout.close();
	fin.close();
	return 0;
}