Cod sursa(job #35828)

Utilizator peanutzAndrei Homorodean peanutz Data 22 martie 2007 16:24:41
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define UNTIL 0.0001
#define NMAX 50010

typedef struct punct
{
double x, y;
};
punct p[NMAX];

long n;
double x, y;
double d;

double distance(double x, double y)
{
	double d = 0;
	long i;

	for(i = 0; i < n; ++i)
	{
		d += sqrt((x-p[i].x)*(x-p[i].x) + (y-p[i].y)*(y-p[i].y));
	}

	return d;
}

void read()
{
	long i;

	scanf("%ld\n", &n);

	for(i = 0; i < n; ++i)
	{
		scanf("%lf %lf\n", &p[i].x, &p[i].y);
		x += p[i].x;
		y += p[i].y;
	}
	x /= n;
	y /= n;

	d = distance(x, y);
}

void search()
{
	double d1, d2, d3, d4;
	double q = 4;

	while(q >= UNTIL)
	{
		d1 = distance(x + q, y);
		d2 = distance(x, y + q);
		d3 = distance(x - q, y);
		d4 = distance(x, y - q);

		if(d > d1)
		{
			x += q;
			d = d1;
		}
		else if(d > d2)
		{
			y += q;
			d = d2;
		}
		else if(d > d3)
		{
			x -= q;
			d = d3;
		}
		else if(d > d4)
		{
			y -= q;
			d = d4;
		}
		else
		{
			q /= 2;
		}
	}
}

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

	read();

	search();

        //x = floor(x*10000)/10000;
	//y = floor(y*10000)/10000;

	printf("%.4lf %.4lf\n", x, y);

	fclose(stdin);
	fclose(stdout);

	return 0;
}