Cod sursa(job #21887)

Utilizator beleap belea belea Data 24 februarie 2007 21:45:50
Problema Adapost 2 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <stdio.h>
#include <math.h>

double a[50001],b[50001], v[16], kkt[] = {-1,0,1};

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,ii,n,e,u1,u2;
   double aprox,X=0,Y=0,d=0,best=0;
   
   v[1]=100;
   v[2]=10;
   v[3]=5;
   v[4]=2;
   v[5]=1;
   v[6]=0.9;
   v[7]=0.3;
   v[8]=0.2;
   v[9]=0.1;
   v[10]=0.01;
   v[11]=0.001;
   v[12]=0.0001;
   v[13]=0.00001;
   

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

     e=1;
     for(u1=0;u1<=2;++u1)
      for(u2=0;u2<=2;++u2)
       {
        for(ii=1;ii<=10 && e;++ii)
        {
         {
          d=0;
          e=0;
          for(i=1;i<=n;++i)
           d+=dist(a[i],b[i],X+kkt[u1]*v[q],Y+kkt[u2]*v[q]);
         
          if(d<best)
           {
            X+=kkt[u1]*v[q];
            Y+=kkt[u2]*v[q];
            best=d;
            e=1;
           }
         }
        }
       }
    }

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

   return 0;
 }