Cod sursa(job #130566)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 1 februarie 2008 15:34:42
Problema Adapost 2 Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <stdio.h>
#include <math.h>

int n;

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

float suma, min;

float dist(double x, double 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 caut()
{
	float pas, d, min = 10000000;
	pas = 10;
	d = dist(p.x, p.y);
	if (min > d) min = d;


	while (pas > 0.0001)
	{
		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 = 10;

	while (pas > 0.0001)
	{
		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;
		}
	}


	pas = 1;
	d = dist(p.x, p.y);
	if (min > d) min = d;


	while (pas > 0.0001)
	{
		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 = 1;

	while (pas > 0.0001)
	{
		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;

	p.x = p.y = 1000;

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

	caut();
	printf("%.4f %.4f\n",p.x, p.y);
	return 0;
}