Cod sursa(job #119135)

Utilizator vlad.maneaVlad Manea vlad.manea Data 29 decembrie 2007 18:28:44
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <stdio.h>
#include <math.h>

#define nmax 50005
#define infinit 3270

int N, i, dir;

long double X[nmax], Y[nmax], minim, dist, d1, d2, xn1, yn1;

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

void read()
{
	freopen("adapost2.in", "r", stdin);
	scanf("%d", &N);
	for (i = 1; i <= N; ++i)
		scanf("%Lf %Lf", X+i, Y+i);
}

void solve()
{
	// calculez centrul de greutate al punctelor (X, Y)
	// for (i = 1; i <= N; ++i) X[0] += X[i]; X[0] /= N;
	// for (i = 1; i <= N; ++i) Y[0] += Y[i]; Y[0] /= N;

	// calculez distantele pana la punct
	for (i = 1; i <= N; ++i)
		d1 += sqrt(X[i]*X[i] + Y[i]*Y[i]);

	for (dist = 100; dist >= 0.00001; dist /= 10)
		for (d2 = 0; d2 <= d1; )
			for (dir = 0; dir < 4; ++dir)
			{
				xn1 = X[0] + dist * dx[dir];
				yn1 = Y[0] + dist * dy[dir];

				for (d2 = 0, i = 1; i <= N; ++i)
					d2 += sqrt((X[i]-xn1)*(X[i]-xn1) + (Y[i]-yn1)*(Y[i]-yn1));

				if (d1 > d2)
				{
					X[0] = xn1;
					Y[0] = yn1;

					d1 = d2;

					break;
				}

			}
}

void write()
{
	freopen("adapost2.out", "w", stdout);
	printf("%Lf %Lf\n", X[0], Y[0]);
}

int main()
{
	read();

	solve();

	write();

	return 0;
}