Cod sursa(job #1118288)

Utilizator mvcl3Marian Iacob mvcl3 Data 24 februarie 2014 09:39:50
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.49 kb
#include <fstream>
#include <cmath>
#include <iomanip>

#define in "adapost2.in"
#define out "adapost2.out"
#define Max_Size 50009
#define eps 0.001

typedef std :: pair < double, double > POINT;

std :: ifstream f(in);
std :: ofstream g(out);

int N;
POINT CG, A[Max_Size];
double best_sol;
short dx[] = {-1, 0, 0, 1};
short dy[] = {0, -1, 1, 0};

inline void Read_Data() {
    f >> N;

    for(int i = 1; i <= N; ++i) {
        f >> A[i].first >> A[i].second;
        CG.first += A[i].first, CG.second += A[i].second;
    }

    CG.first /= N, CG.second /= N;
}

inline double Count_Dist(POINT p) {
    double d = 0;
    for(int i = 1; i <= N; ++i)
        d += sqrt((p.first - A[i].first) * (p.first - A[i].first) + (p.second - A[i].second) * (p.second - A[i].second));
    return d;
}

inline void Solve() {
    best_sol = Count_Dist(CG);
    double d; POINT new_point;

    for(double i = 100; i >= eps; i /= 2) {
        bool ok = 1;

        while(ok) {
            ok = 0;
            for(int k = 0; k < 4; ++k) {
                new_point.first = CG.first + i * dx[k];
                new_point.second = CG.second + i * dy[k];
                d = Count_Dist(new_point);

                if(d < best_sol) {
                    best_sol = d;
                    CG = new_point;
                    ok = 1;
                }
            }
        }
    }
}

int main() {
    Read_Data();
    Solve();

    g << std :: fixed << std :: setprecision(4) << CG.first << ' ' << CG.second << '\n';

    g.close();
    return 0;
}