Cod sursa(job #1054129)

Utilizator ioalexno1Alexandru Bunget ioalexno1 Data 13 decembrie 2013 13:34:11
Problema Adapost 2 Scor 92
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <cstdio>
#include <cmath>
#include <fstream>


using namespace std;

const int MAX_N = 50010, MAX_V = 200,
          dx[4] = { 1, -1, 0, 0 },
          dy[4] = { 0, 0, -1, 1 };
const double prec = 0.0005;
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(){

    for( int i = 1; i <= N; ++i ){

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

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

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

                x_sol = x_sol + dx[i] * v;
                y_sol = y_sol + dy[i] * v;
                dist_min = d;
                continue;
                }
            }
        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;
}