Cod sursa(job #956265)

Utilizator Stefex09Stefan Teodorescu Stefex09 Data 2 iunie 2013 17:38:07
Problema Adapost 2 Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <cstdio>
#include <iostream>
#include <cmath>

using namespace std;

const double EPS = 1e-5;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

struct point
{
    double x, y;
};

int N;
point V[50010];
double X, Y;

inline double dist (const point &A, const point &B)
{
    return double (sqrt ((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y)));
}

inline double total_dist (const point &X)
{
    double ret = 0;
    int i;

    for (i = 1; i <= N; i ++)
        ret += dist (X, V[i]);

    return ret;
}

void Solve ()
{
    point P = {X, Y};
    double best = total_dist (P), now;
    double step = 512.0;
    bool ok;
    int i;

    while (step > EPS){
        ok = 0;

        for (i = 0; i < 4; i ++){
            point S = {P.x + step * dx[i], P.y + step * dy[i]};
            now = total_dist (S);

            if (now < best){
                best = now;
                P = S;
                ok = 1;
                break;
            }
        }

        if (!ok)
            step /= 2.0;
    }
    cout << P.x << " " << P.y;
}

int main()
{
    freopen ("adapost2.in", "r", stdin);
    freopen ("adapost2.out", "w", stdout);

    int i;

    scanf ("%d", &N);

    for (i = 1; i <= N; i ++){
        scanf ("%lf %lf", &V[i].x, &V[i].y);
        X += V[i].x;
        Y += V[i].y;
    }
    X /= N;
    Y /= N;
    Solve ();

    return 0;
}