Cod sursa(job #1054110)

Utilizator ioalexno1Alexandru Bunget ioalexno1 Data 13 decembrie 2013 13:16:18
Problema Adapost 2 Scor 26
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <cstdio>
#include <cmath>
#include <fstream>


using namespace std;

const int MAX_N = 50010, MAX_V = 1000,
          dx[4] = { 1, -1, 0, 0 },
          dy[4] = { 0, 0, 1, -1 };
const double prec = 0.0001;
int N;
double X[MAX_N], Y[MAX_N], x_sol, y_sol ;

void read(){

    freopen( "adapost2.in", "r", stdin );

    scanf( "%d\n", &N );
    for( int i = 1; i <= N; ++i )
        scanf( "%lf %lf\n", &X[i], &Y[i] );

    fclose( stdin );
}

double dist( double l, double r ){

    double d = 0;
    for( int i = 1; i <= N; ++i )
        d += sqrt( ( X[i] - l ) * ( X[i] - l ) + ( Y[i] - r ) * ( Y[i] - r ) );
    return d;
}

void solve(){
    double s_x = 0, s_y = 0;
    for( int i = 1; i <= N; ++i ){

        s_x += X[i];
        s_y += Y[i];
        }
    double v = MAX_V, dist_min = dist( x_sol, y_sol );
    x_sol = s_x / double( N );
    y_sol = s_y / double( N );
    int ind = -1;
    while( v >= prec ){

        for( int i = 0; i < 4; ++i ){

            double l = x_sol + dx[i] * v, r = y_sol + dy[i] * v;
            double d = dist( l, r );
            if( d < dist_min ){

                dist_min = d;
                ind = i;
            }
        }
        if( ind >= 0 ){

            x_sol = x_sol + dx[ind] * v;
            y_sol = y_sol + dy[ind] * v;
        }
        v /= 2;
    }
}

void write(){

    freopen( "adapost2.out", "w", stdout );

    printf( "%.4lf %.4lf", x_sol, y_sol );
    fclose( stdout );
}

int main()
{
    read();
    solve();
    write();
    return 0;
}