Cod sursa(job #130614)

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

int n;

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

float suma, min;

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);
	ifstream in("adapost2.in");

	scanf("%d",&n);

	int i;

	p.x = p.y = 0;

	for (i = 1; i <= n; i++)  scanf("%f %f", &v[i].x, &v[i].y);
	in.close();

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