Cod sursa(job #2082594)

Utilizator andreiiiiPopa Andrei andreiiii Data 6 decembrie 2017 16:31:54
Problema Adapost 2 Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 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 minx = 1000, maxx = -1000, miny = 1000, maxy = -1000;
    for (int i = 0; i < n; ++i) {
        fin >> x[i] >> y[i];
        minx = min(minx, x[i]);
        maxx = max(maxx, x[i]);
        miny = min(miny, y[i]);
        maxy = max(maxy, y[i]);
    }

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

    auto searchX = [&](double y) -> pair<double, double> {
        double lx = minx, rx = maxx;
        for (int it = 0; it < 40; ++it) {
            double v1 = getValue((2 * lx + rx) / 3, y);
            double v2 = getValue((lx + 2 * rx) / 3, y);
            if (v1 < v2) {
                rx = (lx + 2 * rx) / 3;
            } else {
                lx = (2 * lx + rx) / 3;
            }
        }
        return make_pair((lx + rx) * 0.5, getValue((lx + rx) * 0.5, y));
    };
    double ly = miny, ry = maxy;
    for (int i = 0; i < 40; ++i) {
        double v1 = searchX((2 * ly + ry) / 3).second;
        double v2 = searchX((ly + 2 * ry) / 3).second;
        if (v1 < v2) {
            ry = (ly + 2 * ry) / 3;
        } else {
            ly = (2 * ly + ry) / 3;
        }
    }
    double ansx = searchX((ly + ry) * 0.5).first;
    double ansy = (ly + ry) * 0.5;
    fout << setprecision(4) << fixed;
    fout << ansx << ' ' << ansy << '\n';



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