Cod sursa(job #11864)

Utilizator crawlerPuni Andrei Paul crawler Data 1 februarie 2007 23:28:06
Problema Adapost 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <stdio.h>
#include <math.h>

double a[50001],b[50001];

double dist(double x1,double y1,double x2,double y2)
 {
  double x=x1-x2,y=y1-y2;
  x*=x;y*=y;
  return sqrt(x+y);
 }

int main()
 {
   freopen("adapost2.in","r",stdin);
   freopen("adapost2.out","w",stdout);

   long i,n,e;
   double aprox,X=0,Y=0,d=0,best=0;
   
   

   scanf("%ld",&n);

   for(i=1;i<=n;++i)
    {
     scanf("%lf %lf",&a[i],&b[i]);
     X+=a[i]/n;
     Y+=b[i]/n;
    }

   for(i=1;i<=n;++i)
    best+=dist(a[i],b[i],X,Y);
    

   for(aprox=100;aprox>=0,0001;aprox/=10,0)
    {
     e=1;
     while(e)
      {
       e=0;
       //st
       d=0;
       for(i=1;i<=n;++i)
        d+=dist(a[i],b[i],X-aprox,Y);
       if(d<best)
        {
         X-=aprox;
         e=1;
         best=d;
        }
       //dr
       d=0;
       for(i=1;i<=n;++i)
        d+=dist(a[i],b[i],X+aprox,Y);
       if(d<best)
        {
         X+=aprox;
         e=1;
         best=d;
        }
       //sus
       d=0;
       for(i=1;i<=n;++i)
        d+=dist(a[i],b[i],X,Y-aprox);
       if(d<best)
        {
         Y-=aprox;
         e=1;
         best=d;         
        }
       //jos
       d=0;
       for(i=1;i<=n;++i)
        d+=dist(a[i],b[i],X,Y+aprox);
       if(d<best)
        {
         Y+=aprox;
         e=1;
         best=d;         
        }
      }
    }

   printf("%lf %lf\n", X, Y);

   return 0;
 }