Cod sursa(job #130620)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 1 februarie 2008 16:21:35
Problema Adapost 2 Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <stdio.h>
#include <math.h>

int n;

typedef struct
{
	float x, y;
} Punct;
Punct v[50000], 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 = 200;
	d = dist(p.x, p.y);
	min = d;


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

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

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

	}

	pas = 200;

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

		d = dist(p.x, p.y);
		if (min > d && dist(p.x, p.y - pas/2) > 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.00001)
	{
		p.x -= pas;

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

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

	}

	pas = p.y;

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

		d = dist(p.x, p.y);
		if (min > d && dist(p.x, p.y - pas/2) > 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 <= 7; i++)
	{		
		caut1();
		caut2();
	}
	
	printf("%.4f %.4f\n",p.x, p.y);
	return 0;
}