Cod sursa(job #2079935)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 2 decembrie 2017 00:39:02
Problema Adapost 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <bits/stdc++.h>
using namespace std;

constexpr int MAX_COORDINATE = 1000;
constexpr  double EPS = 1e-4;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, 1, -1};

struct point {
    point(double x = 0, double y = 0) :
        x(x), y(y) {
    }
    double x, y;
};

inline point center_of_mass(const vector< point >& points) {
    point center;
    for (auto&& it : points) {
        center.x += it.x;
        center.y += it.y;
    }

    center.x /= points.size();
    center.y /= points.size();

    return center;
}

inline double euclidian_distance(const point& first, const point& second) {
    return sqrt( (first.x - second.x)*(first.x - second.x) + (first.y - second.y)*(first.y - second.y) );
}

inline double evaluate(const point& center, const vector< point >& points) {
    double res = 0;
    for (auto&& it : points)
        res += euclidian_distance(it, center);
    return res;
}

inline void solve() {
    size_t point_count;
    cin >> point_count;

    vector< point > points(point_count);
    for (auto& it : points)
        cin >> it.x >> it.y;

    point best_point = center_of_mass(points);
    double best_evaluation = evaluate(best_point, points);

    for (double jump = MAX_COORDINATE; jump > EPS; jump /= 2) {
        double candidate_evaluation = 1.0 * numeric_limits< int >::max();
        point candidate_point;

        for (int dir = 0; dir < 4; ++dir) {
            point current_point(best_point.x + dx[dir]*jump, best_point.y + dy[dir]*jump);
            double current_evaluation = evaluate(current_point, points);

            if (current_evaluation < candidate_evaluation) {
                candidate_evaluation = current_evaluation;
                candidate_point = current_point;
            }
        }

        if (candidate_evaluation < best_evaluation) {
            best_evaluation = candidate_evaluation;
            best_point = candidate_point;
            jump *= 2;
        }
    }

    cout << setprecision(4) << fixed << best_point.x << ' ' << best_point.y << endl;
}

int main() {
    assert(freopen("adapost2.in", "r", stdin));
    assert(freopen("adapost2.out", "w", stdout));
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    solve();

    return 0;
}