Cod sursa(job #2499062)

Utilizator ArdeleanOficialAlexandru ArdeleanOficial Data 25 noiembrie 2019 11:00:24
Problema Adapost 2 Scor 67
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>
#include <cmath>

using namespace std;

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

const double EPS = 1e-3;
const int N = 5e4 + 7;

struct Point {
    double x, y;
};

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

Point v[N];
int n;

double sumd(Point a) {
    double ans(0);
    for (int i = 1; i <= n; ++i)
        ans += dist(v[i], a);
    return ans;
}

pair < double, double > optim(double x) {///suma si coordonata
    double pas = 512, r(0);
    while (pas > EPS) {
        if (sumd({x, r + pas + EPS}) < sumd({x, r + pas}))
            r += pas;
        pas /= 2;
    }
    return {sumd({x, r + pas + EPS}), r};
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> v[i].x >> v[i].y;
    double pas = 512, r(0);
    while (pas > EPS) {
        if (optim(r + pas + EPS) < optim(r + pas))
            r += pas;
        pas /= 2;
    }
    fout << r << ' ' << optim(r).second << '\n';
    return 0;
}