Cod sursa(job #2499074)

Utilizator ArdeleanOficialAlexandru ArdeleanOficial Data 25 noiembrie 2019 11:18:01
Problema Adapost 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#pragma GCC optimize("O3")
#include <fstream>
#include <cmath>

using namespace std;

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

const double EPS = 1e-4;
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;
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> v[i].x >> v[i].y;
    double pas = 500;
    double x(0), y(0);
    double minsumd(sumd({x, y}));
    while (pas > EPS) {
        double actsumd(sumd({x + pas, y}));
        bool ok(0);
        if (actsumd < minsumd)
            minsumd = actsumd, x += pas, ok = 1;
        actsumd = sumd({x - pas, y});
        if (actsumd < minsumd)
            minsumd = actsumd, x -= pas, ok = 1;
        actsumd = sumd({x, y + pas});
        if (actsumd < minsumd)
            minsumd = actsumd, y += pas, ok = 1;
        actsumd = sumd({x, y - pas});
        if (actsumd < minsumd)
            minsumd = actsumd, y -= pas, ok = 1;
        if (!ok)
            pas /= 2;
    }
    fout << x << ' ' << y << '\n';
    return 0;
}