Cod sursa(job #214097)

Utilizator wefgefAndrei Grigorean wefgef Data 12 octombrie 2008 18:51:10
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <cstdio>
#include <cmath>

const int MAX_N = 50010;
const double EPS = 0.0001;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

struct punct 
{
	double x, y;
};

int n;
punct a[MAX_N];
punct p, p2;
double d;

double dist(punct p)
{
	int i;
	double rez = 0;

	for (i = 1; i <= n; ++i)
		rez += sqrt((p.x - a[i].x) * (p.x - a[i].x) + (p.y - a[i].y) * (p.y - a[i].y));

	return rez;
}

int main()
{
	freopen("adapost2.in", "r", stdin);
	freopen("adapost2.out", "w", stdout);

	scanf("%d", &n);

	int i;
	for (i = 1; i <= n; ++i) scanf("%lf %lf", &a[i].x, &a[i].y);

	p.x = p.y = 0;
	d = dist(p);
	double pas = 512;
	char q;

	while (pas > EPS)
	{
		q = 0;
		for (i = 0; i < 4; ++i)
		{
			p2.x = p.x + dx[i] * pas;
			p2.y = p.y + dy[i] * pas;

			if (d > dist(p2))
			{
				p = p2;
				d = dist(p);
				q = 1;
				break;
			}
		}
		
		if (!q) pas /= 2;
	}

	printf("%lf %lf", p.x, p.y); 

	return 0;
}