Cod sursa(job #1516632)

Utilizator andreea_zahariaAndreea Zaharia andreea_zaharia Data 3 noiembrie 2015 11:56:20
Problema Adapost 2 Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <fstream>
#include <cmath>

using namespace std;

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 () {
    ifstream fin ("adapost2.in");
    ofstream fout ("adapost2.out");

    point crt;
    crt.x = crt.y = 0;

    fin >> N;
    for (int i = 1; i <= N; i++) {
        fin >> v[i].x;
        fin >> v[i].y;
        crt.x += v[i].x;
        crt.y += v[i].y;
    }
    crt.x /= N;
    crt.y /= N;

    double pas = 1000.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;
        }
    }

    fout << crt.x << " " << crt.y << '\n';

    return 0;
}