Cod sursa(job #343093)

Utilizator ProtomanAndrei Purice Protoman Data 24 august 2009 23:37:49
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <algorithm>
#include <stdio.h>
#include <math.h>

#define MAX 50010

using namespace std;

int dirX[] = {-1, 0, 0, 1};
int dirY[] = {0, -1, 1, 0};
int n;
double sx, sy, Gx, Gy;
double x[MAX], y[MAX];

inline double dist2D(double x1, double y1, double x2, double y2)
{
	return sqrt((double) (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

inline double sol(double Gx, double Gy)
{
	double d = 0;

	for (int i = 1; i <= n; i++)
		d += dist2D(Gx, Gy, x[i], y[i]);

	return d;
}

int main()
{
	freopen("adapost2.in", "r", stdin);
	freopen("adapost2.out", "w", stdout);
	
	scanf("%d", &n);

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

		sx += x[i];
		sy += y[i];
	}

	Gx = sx / n;
	Gy = sy / n;

	double dist = sol(Gx, Gy);

	for (double caut = 1024; caut >= 0.0001; caut /= 2)
		for (int dir = 0; dir < 4; dir++)
			if (sol(Gx + dirX[dir] * caut, Gy + dirY[dir] * caut) < dist)
			{
				Gx += dirX[dir] * caut;
				Gy += dirY[dir] * caut;
				dist = sol(Gx, Gy);

				caut *= 2;
				break;
			}

	printf("%.4lf %.4lf\n", Gx, Gy);

	fclose(stdin);
	fclose(stdout);
	return 0;
}