Cod sursa(job #2082596)

Utilizator andreiiiiPopa Andrei andreiiii Data 6 decembrie 2017 16:33:36
Problema Adapost 2 Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <algorithm>
#include <fstream>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;

int main() {
    ifstream fin("adapost2.in");
    ofstream fout("adapost2.out");

    int n;
    fin >> n;
    vector<double> x(n);
    vector<double> y(n);

    double cx = 0, cy = 0;
    for (int i = 0; i < n; ++i) {
        fin >> x[i] >> y[i];
        cx += x[i];
        cy += y[i];
    }
    cx /= n; cy /= n;

    auto getValue = [&](double vx, double vy) -> double {
        double ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += sqrt((vx - x[i]) * (vx - x[i]) + (vy - y[i]) * (vy - y[i]));
        }
        return ans;
    };

    const int dx[] = {-1, 0, 1, 0};
    const int dy[] = {0, 1, 0, -1};

    double coef = 1000;
    double dist = getValue(cx, cy);
    for (int it = 0; it < 30; ++it) {
        int dir = -1;
        double minDist = 1e99;
        for (int i = 0; i < 4; ++i) {
            double nx = cx + dx[i] * coef;
            double ny = cy + dy[i] * coef;
            double cDist = getValue(nx, ny);
            if (cDist < minDist) {
                minDist = cDist;
                dir = i;
            }
        }
        if (minDist < dist) {
            dist = minDist;
            cx += dx[dir] * coef;
            cy += dy[dir] * coef;
        }
        coef *= 0.6;
    }

    fout << setprecision(4) << fixed;
    fout << cx << ' ' << cy << '\n';



    fin.close();
    fout.close();
}