Cod sursa(job #791201)

Utilizator SchumiDumitru Andrei Georgian Schumi Data 23 septembrie 2012 13:00:52
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <cassert>
#include <cmath>
#include <cstdio>

using namespace std;

struct punct {
    double x;
    double y;
};

const int N = 50005;
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {-1, 0, 1, 0};
const double EPS = 0.0001;

int n;
punct sol;
punct p[N];


void read() {
    assert(freopen("adapost2.in", "r", stdin) != NULL);

    assert(scanf("%d", &n) == 1);
    for (int i = 1; i <= n; ++i)
        assert(scanf("%lf %lf", &p[i].x, &p[i].y) == 2);
}

double sumDist(punct x) {
    double sum = 0.0;

    for (int i = 1; i <= n; ++i)
        sum += sqrt((p[i].x - x.x) * (p[i].x - x.x) + (p[i].y - x.y) * (p[i].y - x.y));

    return sum;
}

void solve() {
    sol.x = sol.y = 0.0;

    double dist = sumDist(sol);
    double pas = 1000;
    while (pas > EPS) {
        bool ok = false;
        punct newP;
        for (int i = 0; i < 4; ++i) {
            newP.x = sol.x + dx[i] * pas;
            newP.y = sol.y + dy[i] * pas;
            double newDist = sumDist(newP);
            if (newDist < dist) {
                sol = newP;
                dist = newDist;
                ok = true;
                break;
            }
        }

        if (!ok)
            pas /= 2.0;
    }
}

void write() {
    assert(freopen("adapost2.out", "w", stdout) != NULL);
    printf("%lf %lf", sol.x, sol.y);
}

int main() {
    read();
    solve();
    write();
}