Cod sursa(job #60887)

Utilizator moscaliuc_ovidiuMoscaliuc Ovidiu moscaliuc_ovidiu Data 17 mai 2007 15:19:10
Problema Adapost 2 Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream.h>
#include <math.h>

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

long int n;
double S=50000;
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();
}

void rezolva (double xa, double ya, double k)
{
long int i;
double s=0;
if (k>0.00001)
{
for (i=1; i<=n&&s<S; i++)
	s+=sqrt(pow(e[i].x-(xa+k), 2)+pow(e[i].y-ya, 2));
if (s<S)
{
S=s;
X=xa+k;
Y=ya;
	rezolva (xa+k, ya, k);
}
else
{
s=0;
	for (i=1; i<=n&&s<S; i++)
		s+=sqrt(pow(e[i].x-(xa-k), 2)+pow(e[i].y-ya, 2));
	if (s<S)
	{
	S=s;
	X=xa-k;
	Y=ya;
	rezolva (xa-k, ya, k);
	}
	else
	{
	s=0;
		for (i=1; i<=n&&s<S; i++)
			s+=sqrt(pow(e[i].x-xa, 2)+pow(e[i].y-(ya+k), 2));
		if (s<S)
		{
		S=s;
		X=xa;
		Y=ya+k;
			rezolva (xa, ya+k, k);
		}
		else
		{
		s=0;
			for (i=1; i<=n&&s<S; i++)
				s+=sqrt(pow(e[i].x-xa, 2)+pow(e[i].y-(ya-k), 2));
			if (s<S)
			{
			S=s;
			X=xa;
			Y=ya-k;
				rezolva (xa, ya-k, k);
			}
			else
				rezolva (xa, ya, k/10);
		}
	}
}
}
}

int main ( )
{
citire ( );
rezolva (0, 0, 100);
ofstream g ("adapost2.out");
g<<X<<" "<<Y;
g.close();
return 0;
}