Cod sursa(job #2619603)

Utilizator trifangrobertRobert Trifan trifangrobert Data 28 mai 2020 01:35:00
Problema Adapost 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 50005;
const double EPS = 0.001;
int N;
pair <double, double> points[NMAX];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

double Solve(double x, double y)
{
    double dist = 0;
    for (int i = 1;i <= N;++i)
    {
        double dx = (points[i].first - x);
        double dy = (points[i].second - y);
        dist += sqrt(dx * dx + dy * dy);
    }
    return dist;
}

int main()
{
    ifstream fin("adapost2.in");
    ofstream fout("adapost2.out");
    fin >> N;
    for (int i = 1;i <= N;++i)
        fin >> points[i].first >> points[i].second;
    double bestx = 500, besty = 500, step = 500;
    double best = Solve(bestx, besty);
    while (step >= EPS)
    {
        for (int k = 0;k < 4;++k)
        {
            double nx = bestx + step * dx[k];
            double ny = besty + step * dy[k];
            double ndist = Solve(nx, ny);
            if (ndist < best)
            {
                best = ndist;
                bestx = nx;
                besty = ny;
                step *= 2;
                break;
            }
        }
        step /= 2;
    }
    fout << setprecision(4) << fixed;
    fout << bestx << " " << besty << "\n";
    fin.close();
    fout.close();
    return 0;
}