Cod sursa(job #1599509)

Utilizator Athena99Anghel Anca Athena99 Data 13 februarie 2016 22:20:00
Problema Adapost 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <cmath>
#include <fstream>
#include <iomanip>

using namespace std;

ifstream fin("adapost2.in");
ofstream fout("adapost2.out");

const int nmax= 50000;
const int out_prec= 4;
const int dx[]= {0, 0, 1, -1};
const int dy[]= {1, -1, 0, 0};

double x[nmax+1], y[nmax+1];

double sum( double gx, double gy, int n ) {
    double sol= 0;
    for ( int i= 1; i<=n; ++i ) {
        sol= (double)sol+sqrt((x[i]-gx)*(x[i]-gx)+(y[i]-gy)*(y[i]-gy));
    }

    return sol;
}

int main(  ) {
    double gx= 0, gy= 0;
    int n;
    fin>>n;
    for ( int i= 1; i<=n; ++i ) {
        fin>>x[i]>>y[i];
        gx+= x[i], gy+= y[i];
    }
    gx= (double)gx/n, gy= (double)gy/n;

    double s= sum(gx, gy, n), p= 512;
    for ( int i= 50, ok; i>=0; --i ) {
        ok= 1;
        for ( int j= 0; j<4; ++j ) {
            double a= (double)gx+dx[j]*p, b= (double)gy+dy[j]*p;
            double auxsum= sum(a, b, n);

            if ( s>auxsum ) {
                s= auxsum;
                gx= a, gy= b;
                ok= 0;
                break;
            }
        }

        if ( ok==1 ) {
            p= (double)p/2;
        }
    }

    fout<<setprecision(out_prec)<<fixed;
    fout<<gx<<" "<<gy<<"\n";

    return 0;
}