Cod sursa(job #2070521)

Utilizator flibiaVisanu Cristian flibia Data 19 noiembrie 2017 17:31:09
Problema Adapost 2 Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <bits/stdc++.h>

using namespace std;

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

struct lol{
	double x, y;
};

int n;
double u, d, l, r, x, y, eps = 200, bst;
lol a[50100];

double dist(lol a, lol b){
	return sqrt((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));
}

double get(lol p){
	double s = 0;
	for(int i = 1; i <= n; i++)
		s += dist(p, a[i]);
	return s;
}

int main(){
	in >> n;
	for(int i = 1; i <= n; i++){
		in >> a[i].x >> a[i].y;
		x += a[i].x;
		y += a[i].y;
	}
	x = a[1].x; y = a[1].y;
	bst = get({x, y});
	for(int i = 1; i <= 30; i++, eps /= 2){
		u = get({x - eps, y});
		d = get({x + eps, y});
		l = get({x, y - eps});
		r = get({x, y + eps});
		if(u < min({bst, d, l, r})){
			bst = u;
			x -= eps;
			continue;
		}
		if(d < min({bst, u, l, r})){
			bst = d;
			x += eps;
			continue;
		}
		if(l < min({bst, u, d, r})){
			bst = l;
			y -= eps;
			continue;
		}
		if(r < min({bst, u, d, l})){
			bst = r;
			y += eps;
			continue;		
		}
	}
	out << fixed << setprecision(5) << x << ' ' << y;
	return 0;
}