Cod sursa(job #1516651)

Utilizator andreea_zahariaAndreea Zaharia andreea_zaharia Data 3 noiembrie 2015 12:14:25
Problema Adapost 2 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <cstdio>
#include <cmath>

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

struct point {double x, y;} v[NMAX];
int N;

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

double allDistanceSum (point Q) {
    double ANS = 0;
    for (int i = 1; i <= N; i++) {
        ANS += distance (v[i], Q);
    }
    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", &v[i].x, &v[i].y);
    }

    double pas = 500.0;
    point crt;
    crt.x = crt.y = 500.0;
    double distCrt = allDistanceSum (crt);
    bool modif;

    while (pas > EPS) {
        modif = 0;
        for (int i = 0; i < 4; i++) {
            point tmp;
            tmp.x = crt.x + dx[i] * pas;
            tmp.y = crt.y + dy[i] * pas;

            double distTmp = allDistanceSum (tmp);
            if (distTmp < distCrt) {
                distCrt = distTmp;
                crt = tmp;
                modif = 1;
            }
        }

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

    printf ("%lf %lf\n", crt.x, crt.y);

    return 0;
}