Cod sursa(job #1074776)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 7 ianuarie 2014 22:43:03
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.34 kb
#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<float, float> vec[Nmax], ans, sum;

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

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

	return sqrt(rez);
}

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

	float rez = 0;
	register int i;

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

	return rez;
}

int main() {

	pair<float, float> new_ans;
	float _x, _y, dist, caut;
	register int k, i;

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

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

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

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

	fclose(f);
	fclose(g);

	return 0;
}