Cod sursa(job #1070093)

Utilizator tudorv96Tudor Varan tudorv96 Data 30 decembrie 2013 23:08:04
Problema Adapost 2 Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
#include <cmath>
using namespace std;

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

const int N = 5e4 + 5;

#define x first
#define y second

typedef pair <double, double> coord;

const double dx[4] = {-1, 0, 1, 0},
            dy[4] = {0, 1, 0, -1};
double sol, n;
coord v[N], s, p;

double dist(coord a, coord b) {
    return sqrt ((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));
}

double check(coord P) {
    double sum = 0;
    for (int i = 0; i < n; ++i)
        sum += dist(P, v[i]);
    return sum;
}

int main() {
    fin >> n;
    for (int i = 0; i < n; ++i) {
        fin >> v[i].x >> v[i].y;
        s.x += v[i].x;
        s.y += v[i].y;
    }
    sol = check(s);
    s.x /= n;
    s.y /= n;
    for (double step = 16; step > 1e-4; step /= 2.0) {
        bool ok = 0;
        for (int k = 0; k < 4; ++k) {
            p.x = s.x + step * dx[k];
            p.y = s.y + step * dy[k];
            double crt = check(p);
            if (crt < sol) {
                sol = crt;
                s = p;
                ok = 1;
                break;
            }
        }
        if (ok)
            step *= 2.0;
    }
    fout << p.x << " " << p.y << "\n";
}