Cod sursa(job #1541158)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 3 decembrie 2015 19:55:41
Problema Adapost 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 50000;
const double EPS = 1e-8;
const int D[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };

struct Point  {
    double x, y;
};

Point v[MAX_N];

double sumDistance(const Point &A, const int &N) {
    double s = 0.00;
    for (int i = 0; i < N; i++) {
        s += sqrt((A.x - v[i].x) * (A.x - v[i].x) + (A.y - v[i].y) * (A.y - v[i].y));
    }
    return s;
}

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

    scanf("%d", &N);
    solution.x = 0.00;
    solution.y = 0.00;
    for (int i = 0; i < N; i++) {
        scanf("%lf%lf", &v[i].x, &v[i].y);
        solution.x += v[i].x;
        solution.y += v[i].y;
    }
    solution.x /= N;
    solution.y /= N;

    fclose(stdin);

    double step = 256.00;
    double solDist = sumDistance(solution, N);
    for (int it = 0; it < 46; it++) {
        double x = solution.x;
        double y = solution.y;
        double newStep = step * 0.5;
        for (int i = 0; i < 4; i++) {
            Point tmp = {x + step * D[i][0], y + step * D[i][1]};
            double d = sumDistance(tmp, N);
            if (d < solDist) {
                solDist = d;
                solution = tmp;
                newStep = step;
            }
        }
        step = newStep;
    }

    printf("%.4f %.4f\n", solution.x, solution.y);
    fclose(stdout);
    return 0;
}