Cod sursa(job #792931)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 1 octombrie 2012 17:09:06
Problema Adapost 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <cstdio>
#include <cmath>
#include <cassert>

using namespace std;

const int MaxN = 50005;
const double Eps = 1e-4;
const double MaxR = 512.0;
const double oo = 1000000000.0;
const int DX[] = {0, -1, 0, 1, 0}, DY[] = {0, 0, 1, 0, -1};

struct Point {
    double x, y;

    Point() {
        x = y = 0.0;
    }

    Point(const double x, const double y) {
        this->x = x, this->y = y;
    }
};

Point Points[MaxN], S;
int N;

inline double F(const Point &P) {
    double d = 0.0;
    for (int i = 0; i < N; ++i)
        d += sqrt((Points[i].x-P.x)*(Points[i].x-P.x)+(Points[i].y-P.y)*(Points[i].y-P.y));
    return d;
}

void Solve() {
    Point P;
    for (int i = 0; i < N; ++i)
        P.x += Points[i].x, P.y += Points[i].y;
    P.x /= N, P.y /= N;
    double R = MaxR, MinV = F(P);
    while (R > Eps) {
        int MinD = 0;
        for (int d = 1; d < 5; ++d) {
            double V = F(Point(P.x+R*DX[d], P.y+R*DY[d]));
            if (V < MinV)
                MinD = d, MinV = V;
        }
        if (MinD == 0)
            R *= 0.5;
        else
            P.x += R*DX[MinD], P.y += R*DY[MinD];
    }
    S = P;
}

void Read() {
    assert(freopen("adapost2.in", "r", stdin));
    assert(scanf("%d", &N) == 1);
    for (int i = 0; i < N; ++i)
        assert(scanf("%lf %lf", &Points[i].x, &Points[i].y) == 2);
}

void Print() {
    assert(freopen("adapost2.out", "w", stdout));
    printf("%.4lf %.4lf\n", S.x, S.y);
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}