Cod sursa(job #2031704)

Utilizator robx12lnLinca Robert robx12ln Data 3 octombrie 2017 18:26:41
Problema Adapost 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include<fstream>
#include<cmath>
#include<iomanip>
using namespace std;
ifstream fin("adapost2.in");
ofstream fout("adapost2.out");
const double EPS = 1e-6;
double S, bestS;
int ok = 0;
struct Point{
    double x, y;
} v[50005], P;
int n;
inline double dist( Point A, Point B ){
    return sqrt( ( A.x - B.x ) * ( A.x - B.x ) + ( A.y - B.y ) * ( A.y - B.y ) );
}
inline double area( Point Q ){
    double A = 0.0;
    for( int i = 1; i <= n; i++ )
            A += dist( Q, v[i] );
    return A;
}
void better( Point Q ){
    S = area( Q );
    if( bestS > S ){
        bestS = S;
        P = Q;
        ok = 1;
    }
}
Point make_point( double X, double Y ){
    Point aux;
    aux.x = X, aux.y = Y;
    return aux;
}
int main(){
    fin >> n;
    for( int i = 1; i <= n; i++ ){
        fin >> v[i].x >> v[i].y;
        P.x += v[i].x;
        P.y += v[i].y;
    }
    if( n == 1 ){
        fout << v[1].x << " " << v[1].y;
        return 0;
    }
    P.x /= n;
    P.y /= n;
    bestS = area( P );
    for( double pas = 20.0; pas > EPS; pas /= 2.0 ){
        ok = 0;
        better( make_point( P.x + pas, P.y + pas ) );
        better( make_point( P.x + pas, P.y - pas ) );
        better( make_point( P.x - pas, P.y - pas ) );
        better( make_point( P.x - pas, P.y + pas ) );
        if( ok == 1 )
            pas *= 2.0;
    }
    fout << setprecision(5) << fixed << P.x << " " << P.y;
    return 0;
}