Cod sursa(job #61005)

Utilizator moscaliuc_ovidiuMoscaliuc Ovidiu moscaliuc_ovidiu Data 17 mai 2007 20:41:01
Problema Adapost 2 Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <fstream.h>
#include <math.h>

struct gf
{
double x, y;
}e[50000];

long int n;
double S;
double X, Y;

void citire ( )
{
ifstream f ("adapost2.in");
f>>n;
long int i;
for (i=1; i<=n; i++)
	f>>e[i].x>>e[i].y;
f.close();
}

int main ( )
{
citire ( );
int t=1, p=0;
double xa=0, ya=0, s=0, k=1;
long int i;
for (i=1; i<=n; i++)
{
	xa+=e[i].x;
	ya+=e[i].y;
}
xa/=n;
xa*=10000;
xa=floor(xa);
xa/=10000;
ya/=n;
ya*=10000;
ya=floor(ya);
ya/=10000;
for (i=1; i<=n; i++)
	S+=sqrt((e[i].x-xa)*(e[i].x-xa)+(e[i].y-ya)*(e[i].y-ya));
while (k>0.00001)
{
t=1;
p=0;
	while (t)
	{
	t=0;
	s=0;
		for (i=1; i<=n&&s<S; i++)
			s+=sqrt((e[i].x-(xa+k))*(e[i].x-(xa+k))+(e[i].y-ya)*(e[i].y-ya));
		if (s<S)
		{
		xa+=k;
		S=s;
		X=xa;
		Y=ya;
		t=1;
		p=1;
		}
	}
	t=1;
	while (t)
	{
	t=0;
	s=0;
		for (i=1; i<=n&&s<S; i++)
			s+=sqrt((e[i].x-(xa-k))*(e[i].x-(xa-k))+(e[i].y-ya)*(e[i].y-ya));
		if (s<S)
		{
		xa-=k;
		S=s;
		X=xa;
		Y=ya;
		t=1;
		p=1;
		}
	}
	t=1;
	while (t)
	{
	t=0;
	s=0;
		for (i=1; i<=n&&s<S; i++)
			s+=sqrt((e[i].x-xa)*(e[i].x-xa)+(e[i].y-(ya+k))*(e[i].y-(ya+k)));
		if (s<S)
		{
		ya+=k;
		S=s;
		X=xa;
		Y=ya;
		t=1;
		p=1;
		}
	}
	t=1;
	while (t)
	{
	t=0;
	s=0;
		for (i=1; i<=n&&s<S; i++)
			s+=sqrt((e[i].x-xa)*(e[i].x-xa)+(e[i].y-(ya-k))*(e[i].y-(ya-k)));
		if (s<S)
		{
		ya-=k;
		S=s;
		X=xa;
		Y=ya;
		t=1;
		p=1;
		}
	}
	if (!p)
		k/=1000;
}
ofstream g ("adapost2.out");
g<<X<<" "<<Y;
g.close();
return 0;
}