Cod sursa(job #2549579)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 17 februarie 2020 20:07:51
Problema Adapost 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <bits/stdc++.h>

using namespace std;

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

const int DIM = 5e4 + 7;
const double EPS = 1e-3;

pair <double, double> v[DIM];

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


int n;

double dist(double x, double y)
{
	double ans = 0;
	
	for(int i = 1; i <= n; i++)
	{
		double d1 = x - v[i].first;
		double d2 = y - v[i].second;
		
		ans += sqrt(d1 * d1 + d2 * d2);
	}
	
	return ans;
}



main()
{
	fin >> n;
	
	for(int i = 1; i <= n; i++)
	{
		fin >> v[i].first >> v[i].second;
	}
	
	double x = 0;
	double y = 0;
	
	double ans = dist(0, 0);
	double cat = 1000;
	
	while(cat >= EPS)
	{
		for(int i = 0; i < 4 ; i++)
		{
			double nx = x + cat * dx[i];
			double ny = y + cat * dy[i];
			
			double act = dist(nx, ny);
			
			if(act < ans)
			{
				ans = act;
				x = nx;
				y = ny;
				cat *= 2;
				break;
			}
		}
		
		cat /= 2;
	}
	
	fout << fixed << setprecision(7) << x << ' ' << y << '\n';
}