Cod sursa(job #1070106)

Utilizator tudorv96Tudor Varan tudorv96 Data 30 decembrie 2013 23:21:58
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.34 kb
#include <fstream>
#include <cmath>
using namespace std;

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

const int N = 5e4 + 5;

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.first - a.first) * (b.first - a.first) + (b.second - a.second) * (b.second - a.second));
}

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

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