Cod sursa(job #841446)

Utilizator stoicatheoFlirk Navok stoicatheo Data 24 decembrie 2012 11:22:05
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb

#include<stdio.h>
#include<math.h>

#define maxN 50005
#define eps 1e-4

FILE*f=fopen("adapost2.in","r");
FILE*g=fopen("adapost2.out","w");

int n,i,d; double step,x,y,distmin,aux;
int di[4] = {0,0,-1,1};
int dj[4] = {-1,1,0,0};

struct pct{
    double x;
    double y;
}A[maxN];

inline double sumdist ( double x, double y ){
    double dist = 0;

    for ( i = 1 ; i <= n ; ++i ){
        dist += sqrt( (x - A[i].x) * (x - A[i].x) + (y - A[i].y) * (y - A[i].y) );
    }
    return dist;
}

inline void citire () {

    fscanf(f,"%d",&n);

    for ( i = 1 ; i <= n ; ++i ){
        fscanf(f,"%lf %lf",&A[i].x,&A[i].y);
        x += A[i].x; y += A[i].y;
    }

    x /= n; y /= n;
}

inline void solve () {

    distmin = sumdist(x,y);

    for ( step = 512.0 ; step >= eps ; step /= 2 ){
        for ( d = 0 ; d < 4 ; ++d ){
            if ( (aux = sumdist(x+di[d]*step,y+dj[d]*step) ) < distmin ){
                distmin = aux;
                x += di[d] * step; y += dj[d]*step;
                step *= 2;
                break;
            }
        }
    }

    fprintf(g,"%lf %lf\n",x,y);
}

int main () {

    citire();
    solve();

    fclose(f);
    fclose(g);

    return 0;
}