Cod sursa(job #1541166)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 3 decembrie 2015 20:03:11
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <bits/stdc++.h>

using namespace std;

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

inline char getChar() {
    static char buff[BUFFSIZE];
    static int pos = BUFFSIZE;
    if (pos == BUFFSIZE) {
        fread(buff, 1, BUFFSIZE, stdin);
        pos = 0;
    }
    return buff[pos++];
}

inline double readDouble() {
    double q = 0.00;
    char c;
    do {
        c = getChar();
    } while (!isdigit(c));
    do {
        q = (10 * q) + (c - '0');
        c = getChar();
    } while (isdigit(c));
    for (int i = 10; i < 10000; i = (i << 3) + (i << 1)) {
        c = getChar();
        q = q + (double) (c - '0') / i;
    }
    return q;
}

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++) {
        v[i].x = readDouble();
        v[i].y = readDouble();
        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 < 40; 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;
}