Cod sursa(job #2518736)

Utilizator rapunzelMihnea Andreescu rapunzel Data 6 ianuarie 2020 15:14:49
Problema Adapost 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <fstream>
#include <iomanip>
#include <cmath>

using namespace std;

ifstream cin("adapost2.in");
ofstream cout("adapost2.out");

const int N = 50000 + 7;
const double EPS = 1e-3;
int n;
double x[N];
double y[N];
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};

double get(double a, double b)
{
    double sol = 0;
    for (int i = 1; i <= n; i++)
    {
        double dx = a - x[i];
        double dy = b - y[i];
        sol += sqrt(dx * dx + dy * dy);
    }
    return sol;
}

double a;
double b;
double sol;

void solve(double step)
{
    if (step < EPS)
    {
        return;
    }
    for (int k = 0; k < 4; k++)
    {
        double an = a + step * dr[k];
        double bn = b + step * dc[k];
        double cur = get(an, bn);
        if (cur < sol)
        {
            sol = cur;
            a = an;
            b = bn;
            solve(step);
            return;
        }
    }
    solve(step * 0.5);
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> x[i] >> y[i];
    }
    sol = get(0, 0);
    /// lol, am inteles, ce misto e problema :)))
    /// trebuie sa faci cautraile binare in ac timp, nice
    solve(1000);
    cout << fixed << setprecision(6) << a << " " << b << "\n";
}