Cod sursa(job #338212)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 5 august 2009 14:05:56
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <stdio.h>
#include <math.h>
#define Nmax 50005
#define INF 2000000000

struct punct{
	double x, y;
} a[Nmax],p,G;
int i,n;
double dmin;

double sqr(double x){ return x*x;}
double distanta(punct A,punct B){
	return sqrt(sqr(A.x-B.x)+sqr(A.y-B.y));
}

void read(){
	int i;
	freopen("adapost2.in","r",stdin);
   freopen("adapost2.out","w",stdout);
   scanf("%d",&n);
   for(i=1;i<=n;++i){
      scanf("%lf %lf",&a[i].x,&a[i].y);
      G.x += a[i].x;
      G.y += a[i].y;
   }
   G.x /=n;
   G.y /=n;
   for(i=1;i<=n;++i)
         dmin += distanta(G,a[i]);
}

void caut(){
   int k,ok;
   const int dx[4]={0,0,1,-1}, dy[4]={1,-1,0,0};
	double d =100,dist;

   while(d>=0.0001){
      ok=0;
   	for(k=0;k<4;++k){
      	p.x =G.x+d*double(dx[k]);
      	p.y =G.y+d*double(dy[k]);
         dist=0;
         for(i=1;i<=n;++i)
           dist += distanta(p,a[i]);
         if(dist < dmin){
         	dmin=dist;
            G=p;
            ok=1;
         }
      }
      if(!ok) d/=2;
   }
   printf("%.4f %.4f\n",G.x,G.y);
   fclose(stdin); fclose(stdout);
}

int main(){
	read();
   caut();
   return 0;
}