Cod sursa(job #2280556)

Utilizator ValentinSavoiuFMI Savoiu Valentin-Marian ValentinSavoiu Data 10 noiembrie 2018 20:29:31
Problema Adapost 2 Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>
#include <cmath>
using namespace std;
ifstream f ("adapost2.in");
ofstream g ("adapost2.out");
int N, i;
int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};
double X[50001], Y[50001], xsol, ysol, newx, newy, Pas = 1000, dist, newdist;
double compute_distance (double x, double y, double X, double Y) {
    return sqrt((X - x) * (X - x) + (Y - y) * (Y - y));
}
double compute (double x, double y) {
    double sol = 0;
    for (int i = 1; i <= N; ++i)
        sol = sol + compute_distance(x, y, X[i], Y[i]);
    return sol;
}
int main()
{
    f >> N;
    for (i = 1; i <= N; ++i) {
        f >> X[i] >> Y[i];
        xsol += X[i];
        ysol += Y[i];
    }
    xsol = xsol * 1.0 / N;
    ysol = ysol * 1.0 / N;
    dist = compute(xsol, ysol);
    while (Pas > 0.001) {
        for (i = 0; i < 4; ++i) {
            newx = xsol + Pas * dx[i];
            newy = ysol + Pas * dy[i];
            newdist = compute(newx, newy);
            if (newdist < dist) {
                dist = newdist;
                xsol = newx;
                ysol = newy;
            }
        }
        Pas /= 2;
    }
    g << xsol << ' ' << ysol;
    return 0;
}