Cod sursa(job #11848)

Utilizator crawlerPuni Andrei Paul crawler Data 1 februarie 2007 22:17:40
Problema Adapost 2 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <stdio.h>
#include <math.h>

double a[50001],b[50001], v[16];

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;
   
   v[1]=100;
   v[2]=10;
   v[3]=1;
   v[4]=0,1;
   v[5]=0,01;
   v[6]=0,001;
   v[7]=0,0001;

   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(int q=1;q<=7;++q)
    {

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

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

   return 0;
 }