Cod sursa(job #63496)

Utilizator gigi_becaliGigi Becali gigi_becali Data 28 mai 2007 22:31:49
Problema Adapost 2 Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <cstdio>
#include <cmath>
#define maxc 8
#define maxn 50001
#define eps 0.00000001
struct nod { double x, y;};

nod a[maxn];
int n;

void citire()
{
	freopen("adapost2.in", "r",stdin);
	scanf("%d\n", &n);
	for(int i=1;i<=n;++i) 
	{
		scanf("%lf %lf\n", &a[i].x, &a[i].y);
	}
}

double dist(double x, double y)
{
	double sum=0;
	for(int i=1;i<=n;++i) sum+=sqrt((x-a[i].x)*(x-a[i].x)+(y-a[i].y)*(y-a[i].y));
	return sum;
}


void solve()
{
	int i, j;
	double x=0, y=0, c=maxc;
	double xx, yy;
	double sum=0, S;
	for(i=1;i<=n;++i) x+=a[i].x, y+=a[i].y;
	x=x/(double)n;
	y=y/(double)n;
	S=dist(x, y);
	
	while(c>eps)
	{
		xx=x+c;
		yy=y;
		sum=dist(xx, yy);
		if(S-sum>eps)S=sum, x=xx, y=yy;
		
		
		xx=x-c;
		yy=y;
		sum=dist(xx, yy);
		if(S-sum>eps)S=sum, x=xx, y=yy;
		
		xx=x;
		yy=y+c;
		sum=dist(xx, yy);
		if(S-sum>eps)S=sum, x=xx, y=yy;
		
		xx=x;
		yy=y-c;
		sum=dist(xx, yy);
		if(S-sum>eps)S=sum, x=xx, y=yy;
		/*
		xx=x+c;
		yy=y+c;
		sum=dist(xx, yy);
		if(sum<S)S=sum, x=xx, y=yy;
		
		xx=x-c;
		yy=y+c;
		sum=dist(xx, yy);
		if(sum<S)S=sum, x=xx, y=yy;
		
		xx=x+c;
		yy=y-c;
		sum=dist(xx, yy);
		if(sum<S)S=sum, x=xx, y=yy;
		
		xx=x-c;
		yy=y-c;
		sum=dist(xx, yy);
		if(sum<S)S=sum, x=xx, y=yy;
		*/
	c=c/2;	
	}
	
	printf("%4lf %4lf\n", x, y);
}
		
int main()
{
	freopen("adapost2.out", "w", stdout);
	citire();
	solve();
	return 0;
}