Cod sursa(job #341352)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 18 august 2009 11:23:52
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<stdio.h>
#include<math.h>
#define eps 0.0001
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
struct point 
{
	double x,y;
};
int n,ok;
double d;
point p,p2;
point v[50005];

double dist_p(point a, point b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double dist(point p)
{
	int i;
	double sol=0.0;
	for(i=1;i<=n;++i)
		sol+=dist_p(p,v[i]);
	return sol;
}

int main()
{
	freopen("adapost2.in", "r", stdin);
	freopen("adapost2.out", "w", stdout);
	scanf("%d",&n);
	int i;
	for(i=1;i<=n;++i)
		scanf("%lf %lf",&v[i].x,&v[i].y);
	d=dist(p);
	double pas=1<<9;
	while(pas>eps)
	{
		ok=0;
		for(i=0;i<=3;i++)
		{
			p2.x=p.x+dx[i]*pas;
			p2.y=p.y+dy[i]*pas;
			if(d>dist(p2))
			{
				p=p2;
				d=dist(p);
				ok=1;
				break;
			}
		}
		if(ok==0)
			pas/=2;
	}
	printf("%lf %lf",p.x,p.y); 
	return 0;
}