Cod sursa(job #979166)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 31 iulie 2013 21:57:42
Problema Adapost 2 Scor 92
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <cstdio>
#include <cmath>
using namespace std;

const int MAX_N = 50002;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
const double EPS = 0.001;

typedef struct point {
    double x, y;
};

int N;
double Xst, Yst, TDist = 999999999999, pas = 10000;
point v[MAX_N];

inline double dist(point a, point b) {
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

inline int double_cmp(double a, double b) {
    if(a - b < -EPS)
        return -1;
    if(a - b > EPS)
        return 1;
    return 0;
}

inline void compute() {
    while(double_cmp(pas, EPS) > 0) {
        double temp = TDist, X, Y;
        for(int i = 0; i < 4; ++i) {
            double x = Xst + dx[i]*pas, y = Yst + dy[i]*pas, Dist = 0;
            point A;
            A.x = x, A.y = y;
            for(int i = 1; i <= N; ++i)
                Dist += dist(A, v[i]);
            if(double_cmp(Dist, TDist) < 0)
                TDist = Dist, X = x, Y = y;
        }

        if(double_cmp(TDist, temp) == 0)
            pas = (double) (pas / 2.0);
        else Xst = X, Yst = Y;
    }
}

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

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

    compute();

    printf("%.4lf %.4lf\n", Xst, Yst);

    fclose(stdin);
    fclose(stdout);

    return 0;
}