Cod sursa(job #1846871)

Utilizator Vali_DeaconuVali Deaconu Vali_Deaconu Data 14 ianuarie 2017 07:53:08
Problema Adapost 2 Scor 2
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
# include <fstream>
# include <vector>
# include <iomanip>
# include <cmath>

using namespace std;

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

const int INF = (1<<30);
vector < pair<double, double> > P;
int N;
double xg, yg; // coordonate centru de greutate
double xsol, ysol; // coordonate apropiere
double xfin, yfin; // cordonate apropiere minime
double minAbs, minTmp;
int di[] = {0, 0, 1, -1};
int dj[] = {1, -1, 0, 0};

double suma(double x, double y) {
    double sum = 0;
    for (int i=0; i<N; i++) {
        sum += sqrt ( (x - P[i].first)*(x - P[i].first)+(y - P[i].second)*(y - P[i].second));
    }
    return sum;
}

int main() {
    double x, y, s;

    fin >> N;
    for (int i=1; i<=N; i++) {
        fin >> x >> y;
        P.push_back(make_pair(x, y));
        xg += x;
        yg += y;
    }

    xg /= N;
    yg /= N;
    minAbs = suma(xg, yg);

    for (double k = 10; k >= 0.00001; k /= 10) {
        minTmp = INF;
        for (int d=0; d<=3; d++) {
            x = xg + di[d] * k;
            y = yg + dj[d] * k;
            s = suma(x, y);
            if (s < minTmp) {
                minTmp = s;
                xsol = x;
                ysol = y;
            }
        }

        if (minTmp < minAbs) {
            minAbs = minTmp;
            xfin = xsol;
            yfin = ysol;
        }
    }

    fout << fixed << setprecision(4) << xfin << " " << yfin;
    return 0;
}