Cod sursa(job #2548117)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 16 februarie 2020 11:20:57
Problema Adapost 2 Scor 80
Compilator cpp-64 Status done
Runda amcontrolerdexboxdinmall Marime 1.19 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, -1, -1, 1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, 1, -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 < 8; 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;
		 
		 best += dist(0, 0, vec[i].first, vec[i].second);
	 }
	 
	 double cat = 1000;
	 
	 for(int pas = 1; pas <= 50; pas++, cat /= 2)
	 {
		 update(x, y, cat, n, best);
	 }
	 
	 fout << fixed << setprecision(7) << x << ' ' << y << '\n';
}