Cod sursa(job #2377337)

Utilizator silviu982001Borsan Silviu silviu982001 Data 9 martie 2019 19:54:02
Problema Adapost 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <bits/stdc++.h>

using namespace std;

vector<pair<double, double>> v;
int n;
double x, y, dist;

const vector<pair<int, int>> coord {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

inline double sqr(double x)
{
    return pow(x, 2);
}

void calculeaza(double dd, double &xx, double &yy, double &distanta, bool isFirst)
{
    if (isFirst)
    {
        xx = yy = 0;
        for (int i = 0; i < n; ++i)
        {
            xx += v[i].first * dd;
            yy += v[i].second * dd;
        }

        xx /= n;
        yy /= n;
    }

    distanta = 0;

    for (int i = 0; i < n; ++i)
    {
        distanta += sqrt(sqr(xx-v[i].first) + sqr(yy-v[i].second));
    }
}

int main()
{
    ifstream fin("adapost2.in");
    fin >> n;
    int i;
    double xx, yy, cDist;
    for (i = 0; i < n; ++i)
    {
        fin >> x >> y;
        v.push_back({x, y});
    }
    fin.close();
    calculeaza(1.0, x, y, dist, true);
    xx = x;
    yy = y;
    for (double dd = 1000; dd > 0.001;)
    {
        bool ok = false;
        for (i = 0; i < 4; ++i)
        {
            xx = x + coord[i].first * dd;
            yy = y + coord[i].second * dd;
            calculeaza(dd, xx, yy, cDist, false);
            if (cDist < dist)
            {
                ok = true;
                dist = cDist;
                x = xx;
                y = yy;
            }
        }

        if (!ok)
            dd /= 2;
    }
    ofstream fout("adapost2.out");
    fout.setf(ios::fixed, ios::floatfield);
    fout.precision(4);
    fout << x << " " << y;
    fout.close();
    return 0;
}