Cod sursa(job #1043844)

Utilizator Teodor94Teodor Plop Teodor94 Data 28 noiembrie 2013 23:19:23
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <cstdio>
#include <cmath>
#include <vector>

using namespace std;

#define MAX_N 50000
#define x first
#define y second
#define MAX_STEP 100
#define EPS 0.001

const double dx[] = { 1, 1, 1, 0, -1, -1, -1, 0 };
const double dy[] = { -1, 0, 1, 1, 1, 0, -1, -1 };

pair< double, double > v[MAX_N];

void read( FILE *fin, int &n ) {
    fscanf( fin, "%d", &n );
    for ( int i = 0; i < n; ++i )
        fscanf( fin, "%lf %lf", &v[i].x, &v[i].y );
}

double square( double a ) {
    return a * a;
}

double dist( pair< double, double > a, pair< double, double > b ) {
    return sqrt( square( a.x - b.x ) + square( a.y - b.y ) );
}

pair< double, double > starting_point( int n ) {
    pair< double, double > point = make_pair( 0 , 0 );
    for ( int i = 0; i < n; ++i ) {
        point.x += v[i].x;
        point.y += v[i].y;
    }
    point.x /= n;
    point.y /= n;

    return point;
}

double sum_dist( pair< double, double > a, int n ) {
    double sum = 0;
    for ( int i = 0; i < n; ++i )
        sum += dist( a, v[i] );
    return sum;
}

pair< double, double > solve( int n ) {
    double step = MAX_STEP;
    pair< double, double > best_point = starting_point( n );
    double min_dist = sum_dist( best_point, n );

    while ( step > EPS ) {
        pair< double, double > next_best_point = best_point;
        for ( int i = 0; i < 8; ++i ) {
            pair< double, double > next_point = best_point;
            next_point.first += dx[i] * step;
            next_point.second += dy[i] * step;

            double next_dist = sum_dist( next_point, n );
            if ( next_dist < min_dist ) {
                min_dist = next_dist;
                next_best_point = next_point;
            }
        }

        best_point = next_best_point;

        step /= 2;
    }

    return best_point;
}

int main() {
    FILE *fin, *fout;

    fin = fopen( "adapost2.in", "r" );
    int n;
    read( fin, n );
    fclose( fin );

    fout = fopen( "adapost2.out", "w" );
    pair< double, double > ans = solve( n );
    fprintf( fout, "%.4lf %.4lf\n", ans.x, ans.y );
    fclose( fout );
}