Cod sursa(job #1517001)

Utilizator andreea_zahariaAndreea Zaharia andreea_zaharia Data 3 noiembrie 2015 19:35:53
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <cstdio>
#include <cmath>

const int EPS = 0.0001;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const int NMAX = 50010;

double vx[NMAX], vy[NMAX];
int N;

double distance (double ax, double ay, double bx, double by) {
    return sqrt ( (ax - bx) * (ax - bx) + (ay - by) * (ay - by) );
}

double allDistanceSum (double Qx, double Qy) {
    double ANS = 0;
    for (int i = 1; i <= N; i++) {
        ANS += distance (vx[i], vy[i], Qx, Qy);
    }
    return ANS;
}

int main () {
    freopen ("adapost2.in", "r", stdin);
    freopen ("adapost2.out", "w", stdout);

    scanf ("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf ("%lf%lf", &vx[i], &vy[i]);
    }

    double pas = 500.0;
    double crtx, crty;
    crtx = crty = 500.0;
    double distCrt = allDistanceSum (crtx, crty);
    bool modif;
    int done = 0;

    while (done <= 40) {
        modif = 0;
        for (int i = 0; i < 4; i++) {
            double tmpx, tmpy;
            tmpx = crtx + dx[i] * pas;
            tmpy = crty + dy[i] * pas;

            double distTmp = allDistanceSum (tmpx, tmpy);
            if (distTmp < distCrt) {
                distCrt = distTmp;
                crtx = tmpx;
                crty = tmpy;
                modif = 1;
            }
        }

        if ( !modif) {
            pas /= 2.0;
        }
        done++;
    }

    printf ("%lf %lf\n", crtx, crty);

    return 0;
}