Cod sursa(job #1552029)

Utilizator algebristulFilip Berila algebristul Data 17 decembrie 2015 02:39:55
Problema Adapost 2 Scor 18
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

int N;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
double X[50005];
double Y[50005];

const int ITER = 100;

double dist(int x, int y, int x1, int y1) {
    return sqrt((x1-x)*(x1-x) + (y1-y)*(y1-y));
}

double sumd(int x, int y) {
    double ans = 0;
    for (int i = 1; i <= N; i++) {
        ans += dist(X[i], Y[i], x, y);
    }

    return ans;
}

pair<double, double> solve(double x, double y, double step) {
    int it = ITER;
    double s = sumd(x, y);
    while (it--) {
        double x_ = x, y_ = y, s_ = s;
        int k_ = -1;
        for (int k = 0; k < 4; k++) {
            double x1 = min(max(x + dx[k] * step, 0.), 1000.);
            double y1 = min(max(y + dy[k] * step, 0.), 1000.);
            if (sumd(x1, y1) < s_) {
                s_ = sumd(x1, y1);
                x_ = x1;
                y_ = y1;
                k_ = k;
                break;
            }
        }

        x = x_;
        y = y_;
        s = s_;
        step /= 2;
    }

    return make_pair(x, y);
}

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

    const double initstep = 500;

    double xG = 0, yG = 0;
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%lf %lf", &X[i], &Y[i]);
        xG += X[i], yG += Y[i];
    }

    xG /= N;
    yG /= N;

    pair<double, double> ans = solve(xG, yG, initstep);
    //fprintf(stderr, "%lf %lf\n", sumd(4.14, 4.28), sumd(ans.first, ans.second));

    printf("%.4lf %.4lf\n", ans.first, ans.second);
    return 0;
}