Cod sursa(job #935452)

Utilizator rudarelLup Ionut rudarel Data 3 aprilie 2013 14:59:12
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include<math.h>
#include<stdio.h>
#define fin  "adapost2.in"
#define fout "adapost2.out"
#define Nmax 50001
double v[Nmax][2],field,x,y,best;
int n;
FILE *in,*out;
 
double distance(double x1,double y1,double x2,double y2) {
double a,b;
    a=x1-x2;
    b=y1-y2;
    return sqrt(a*a+b*b);
}
 
int test(double x,double y) {
double tot;
int i;
    tot=0.0;
    for (i=1;i<=n;++i)
        tot+=distance(v[i][0],v[i][1],x,y);
     
    if (tot<best) {
        best=tot; return 1;
    }
 
    return 0;
}
 
void search() {
 
    if (test(x-field,y)) {
        x-=field;
        search();
        return ;
    }
 
    if (test(x,y-field)) {
        y-=field;
        search();
        return ;
    }
     
    if (test(x+field,y)) {
        x+=field;
        search();
        return ;
    }
 
    if (test(x,y+field)) {
        y+=field;
        search();
        return ;
    }
     
    //printf("%lf %lf\n",x,y);
 
    field/=10.0;
 
    if (field<0.0001) return ;
     
    else search();
 
}
 
int main() {
int i,j;
    in=fopen(fin,"r"); out=fopen(fout,"w");
     
    fscanf(in,"%i",&n);
     
    for (i=1;i<=n;++i) fscanf(in,"%lf%lf",&v[i][0],&v[i][1]);
     
    best=100000000000000.0;
 
    field=100.0;
 
    //printf("%lf\n",best);
 
    search();
 
    fprintf(out,"%lf %lf\n",x,y);
 
    return 0;
}