Cod sursa(job #344020)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 28 august 2009 11:00:11
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <stdio.h>
#include <math.h>
#define N 1<<16
#define aprox 0.0001
int n,ok;
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
struct coord
{
	double x,y;
};
coord v[N];
coord pct,pct2;
double distanta,pas;
void read()
{
	scanf("%d",&n);
	int i;
	for (i=1; i<=n; i++)
		scanf("%lf%lf",&v[i].x,&v[i].y);
}
double dist_pcte(coord a,coord b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double dist(coord pct)
{
	double rez=0;
	int i;
	for (i=1; i<=n; i++)
		rez+=dist_pcte(pct,v[i]);
	return rez;
}
void solve()
{
	distanta=dist(pct);
	pas=1<<10;
	int i;
	double t;
	while (pas>aprox)
	{
		ok=0;
		for (i=0; i<4; i++)
		{
			pct2.x=pct.x+dx[i]*pas;
			pct2.y=pct.y+dy[i]*pas;
			t=dist(pct2);
			if (distanta>t)
			{
				distanta=t;
				pct=pct2;
				ok=1;
				break;
			}
		}
		if (!ok)
			pas/=2;
	}
	printf("%lf %lf",pct.x,pct.y);
}
int main()
{
	freopen("adapost2.in","r",stdin);
	freopen("adapost2.out","w",stdout);
	read();
	solve();
	return 0;
}