Cod sursa(job #130791)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 1 februarie 2008 22:05:50
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <stdio.h>
#include <math.h>

int n;

typedef struct
{
	float x, y;
} Punct;
Punct v[50002], p;

float sx, sy;

double dist(float x, float y)
{
	int i;
	double suma = 0;
	for (i = 1; i <= n; i++)
		suma += sqrt((x - v[i].x) * (x - v[i].x) + (y - v[i].y) * (y - v[i].y));
	return suma;
}

void caut1()
{
	double pas, d, min;
	pas = 1;
	d = dist(p.x, p.y);
	min = d;


	while (pas >= 0.0001)
	{
		p.x += pas;

		d = dist(p.x, p.y);

		if (d < min ) min = d;
		else
		{
			p.x -= pas;
			pas /= 2;
		}

	}

	pas = 1;

	while (pas >= 0.0001)
	{
		p.y += pas;

		d = dist(p.x, p.y);
		if (min > d ) min = d;
		else
		{
			p.y -= pas;
			pas /= 2;
		}
	}
}

void caut2()
{
	double pas, d, min;
	pas = p.x;
	d = dist(p.x, p.y);
	min = d;

	while (pas >= 0.0001)
	{
		p.x -= pas;

		d = dist(p.x, p.y);

		if (d < min) min = d;
		else
		{
			p.x += pas;
			pas /= 2;
		}

	}

	pas = p.y;

	while (pas >= 0.0001)
	{
		p.y -= pas;

		d = dist(p.x, p.y);
		if (min > d ) min = d;
		else
		{
			p.y += pas;
			pas /= 2;
		}
	}
}

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

	scanf("%d",&n);

	int i;

	for (i = 1; i <= n; i++)
	{
		scanf("%f %f", &v[i].x, &v[i].y);
		sx += v[i].x;
		sy += v[i].y;
	}

	p.x = sx / n;
	p.y = sy / n;
	

	for (i = 1; i <= 10; i++)
	{		
		caut1();
		caut2();
	}
	
	printf("%.4f %.4f\n",p.x, p.y);
	return 0;
}