Cod sursa(job #1046580)

Utilizator Robert29FMI Tilica Robert Robert29 Data 3 decembrie 2013 09:59:47
Problema Adapost 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include<stdio.h>
#include<math.h>
FILE*f=fopen("adapost2.in","r");
FILE*g=fopen("adapost2.out","w");
int n;
struct punct
{
	double x,y;
} v[50001];
double dist(double x1,double y1,double x2,double y2)
{
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double calc(double x,double y)
{
	double sum=0;
	for(int i=1;i<=n;++i)
		sum+=dist(x,y,v[i].x,v[i].y);
	return sum;
}
double min(double a,double b)
{
	if(a<b)
		return a;
	return b;
}
int main()
{
	fscanf(f,"%d",&n);
	for(int i=1;i<=n;++i)
		fscanf(f,"%lf%lf",&v[i].x,&v[i].y);
	
	int ok=1;
	double x=5000;
	double y=5000;
	double p=5000;
	double sum=calc(x,y);
	while(p>=0.0005)
	{
		
		double sum1,sum2,sum3,sum4;
		x-=p;
		sum1=calc(x,y);
		x+=p;
		
		x+=p;
		sum2=calc(x,y);
		x-=p;
		
		y-=p;
		sum3=calc(x,y);
		y+=p;
		
		y+=p;
		sum4=calc(x,y);
		y-=p;
		
		double sums=min(min(sum1,sum2),min(sum3,sum4));
		if(sum>sums)
		{
			if(sums==sum1)
				x-=p;
			else if(sums==sum2)
				x+=p;
			else if(sums==sum3)
				y-=p;
			else
				y+=p;
			sum=sums;
		}
		else
			p/=2;
	}
	
	fprintf(g,"%.4lf %.4lf",x,y);
	
	fclose(f);
	fclose(g);
	return 0;
}