Cod sursa(job #1074770)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 7 ianuarie 2014 22:37:05
Problema Adapost 2 Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <utility>

using namespace std;

#define x first
#define y second

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

FILE *f = fopen("adapost2.in", "r");
FILE *g = fopen("adapost2.out", "w");

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;

	fscanf(f, "%d", &n);

	for (i = 1; i <= n; i++) {
		fscanf(f, "%lf %lf", &_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;
			}

	fprintf(g, "%lf %lf\n", ans.x, ans.y);

	fclose(f);
	fclose(g);

	return 0;
}