Cod sursa(job #459317)

Utilizator SpiderManSimoiu Robert SpiderMan Data 29 mai 2010 11:08:05
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <cstdio>
#include <cmath>

const char FIN[] = "adapost2.in";
const char FOU[] = "adapost2.out";

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

const int MAX = 500005;
const double ERR = 0.0001;

struct soldat
{
    double I, J;
};

int N;

soldat V[MAX];
soldat soli, soly;

inline double SQ ( double x )
{
    return x * x;
}

double solve( soldat a, soldat b )
{
    return sqrt( SQ (a.I - b.I) + SQ (a.J - b.J) );
}

double dist( soldat x )
{
    double rez = 0;

    for (int i = 1; i <= N; ++i)
        rez += solve(x, V[i]);

    return rez;
}

int main()
{
    freopen(FIN, "r", stdin);
    freopen(FOU, "w", stdout);

    scanf("%d", &N);

    for (int i = 1; i <= N; ++i)
        scanf("%lf %lf", &V[i].I, &V[i].J);

    double max = dist( soli );

    bool q = 1;

    for ( double j = 512 ; j > ERR ; (q ? j /= 2 : 0.0), q = 1 )
    {
        for (int i = 0; i < 4; ++i)
        {
            soly.I = soli.I + dx[i] * j;
            soly.J = soli.J + dy[i] * j;

            if ( max > dist( soly ) )
            {
                max = dist( soli = soly ), q = 0;
                break;
            }
        }
    }

    printf("%.4lf %.4lf", soli.I, soli.J);

    return 0;
}