Cod sursa(job #1416766)

Utilizator smaraldaSmaranda Dinu smaralda Data 8 aprilie 2015 21:46:26
Problema Adapost 2 Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include<stdio.h>
#include<math.h>

const int NMAX = 50005;
const double eps = 1.e-9, INF = 2e9;

int n, dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
double xSol, ySol, x[NMAX], y[NMAX];

double dist (double x1, double y1, double x2, double y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

double sumDist (double x0, double y0) {
    double sum;
    int i;

    sum = 0;
    for(i = 1; i <= n; ++ i)
        sum += dist(x0, y0, x[i], y[i]);
    return sum;
}

int main() {
    freopen("adapost2.in", "r", stdin);
    freopen("adapost2.out", "w", stdout);
    int i, dir, change;
    double step, dmin, val;

    scanf("%d", &n);
    for(i = 1; i <= n; ++ i)
        scanf("%lf%lf", &x[i], &y[i]);

    step = xSol = ySol = 500;
    dmin = INF;
    for(i = 1; i <= 100; ++ i) {
        change = 0;
        for(dir = 0; dir < 4; ++ dir) {
            val = sumDist(xSol + step * dx[dir], ySol + step * dy[dir]);
            if(val < dmin) {
                dmin = val;
                xSol += step * dx[dir];
                ySol += step * dy[dir];

                change = 1;
                break;
            }
        }

        if(!change)
            step /= 2;
    }

    printf("%lf %lf\n", xSol, ySol);
    return 0;
}