Cod sursa(job #2548173)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 16 februarie 2020 12:45:57
Problema Adapost 2 Scor 82
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <bits/stdc++.h>

using namespace std;

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

const int DIM = 5e4 + 7;

pair <double, double> vec[DIM];

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

double dist(double x1, double y1, double x2, double y2)
{
	double ans = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
	ans = sqrt(ans);
	
	return ans;
}

void update(double &x, double &y, double cat, int n, double &best)
{
	int it = -1;
	
	for(int i = 0; i < 4; i++)
	{
		double nx = x + dx[i] * cat;
		double ny = y + dy[i] * cat;
		
		double act = 0;
		
		for(int i = 1; i <= n; i++)
			act += dist(nx, ny, vec[i].first, vec[i].second);
		
		if(act < best)
		{
			best = act;
			it = i;
		}
	}
	
	if(it != -1)
	{
		x += dx[it] * cat;
		y += dy[it] * cat;
	}
}

main()
{
	int n;
	fin >> n;
	
	double x = 0;
	double y = 0;
	
	double best = 0;
	
	for(int i = 1; i <= n; i++)
	{
		fin >> vec[i].first >> vec[i].second;
		
		x += vec[i].first;
		y += vec[i].second;
	}
	
	x /= n;
	y /= n;
	
	for(int i = 1; i <= n; i++)
	{
		best += dist(x, y, vec[i].first, vec[i].second);
	}
	
	double cat = 1000;
	
	for(int pas = 1; pas <= 35; pas++, cat /= 2)
	{
		update(x, y, cat, n, best);
	}
	
	fout << fixed << setprecision(7) << x << ' ' << y << '\n';
}