Cod sursa(job #1074766)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 7 ianuarie 2014 22:33:08
Problema Adapost 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <utility>

using namespace std;

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

#define x first
#define y second

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

int n;
pair<double, double> vec[Nmax], ans, sum;

inline double dist_p(const pair<double, double> &a, const pair<double, double> &b) {

	double rez = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);

	return sqrt(double(rez));
}

inline double sol(const pair<double, double> &point) {

	double rez = 0;
	int i;

	for (i = 1; i <= n; i++)
		rez += dist_p(point, vec[i]);

	return rez;
}

int main() {

	double _x, _y, dist, caut;
	int k, i;

	f >> n;

	for (i = 1; i <= n; i++) {
		f >> _x >> _y;
		vec[i] = make_pair(_x, _y);
		sum.x += vec[i].x;
		sum.y += vec[i].y;
	}

	ans.x = sum.x / n;
	ans.y = sum.y / n;

	dist = sol(ans);

    // g << sum.x << " " << sum.y << " " << ans.x << " " << ans.y << "\n";

	for (caut = 1024; caut >= 0.0001; caut /= 2)
		for (k = 0; k < 4; k++)
			if (sol(make_pair(ans.x + dx[k] * caut, ans.y + dy[k] * caut))
					< dist) {
				ans.x += dx[k] * caut;
				ans.y += dy[k] * caut;
				dist = sol(ans);
				caut *= 2;
				break;
			}

	g << ans.x << " " << ans.y << "\n";

    f.close();
    g.close();

	return 0;
}