Cod sursa(job #1841803)

Utilizator mariusn01Marius Nicoli mariusn01 Data 6 ianuarie 2017 00:58:57
Problema Adapost 2 Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>
#include <cmath>
#include <iomanip>

using namespace std;
int di[] = {0,0,1,-1};
int dj[] = {1,-1,0,0};

int n;
struct punct {
    double x;
    double y;
};

punct p[50010];
double sx, sy, minim, x, y, xnext, ynext, minimCrt;

double suma(double x, double y) {
    double sum = 0;
    for (int i=1;i<=n;i++) {
        sum += sqrt(  (x-p[i].x) * (x-p[i].x) + (y-p[i].y) * (y-p[i].y) );
    }
    return sum;
}

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

    fin>>n;
    for (int i=1;i<=n;i++) {
        fin>>p[i].x>>p[i].y;
        sx += p[i].x;
        sy += p[i].y;
    }
    sx /= n;
    sy /= n;
    minim = suma(sx, sy);
    for (double pas = 500;pas>=0.000001;pas /= 2) {
        minimCrt = 50000000;
        for (int d = 0; d <4; d++) {
            x = sx + di[d] * pas;
            y = sy + dj[d] * pas;
            double s = suma(x, y);
            if (s < minimCrt) {
                minimCrt = s;
                xnext = x;
                ynext = y;
            }
        }
        //if (sqrt(  (sx-xnext) * (sx-xnext) + (sy-ynext) * (sy-ynext) ) <= 0.00001)
        //    break;

        if (minimCrt < minim) {
            sx = xnext;
            sy = ynext;
            minim = minimCrt;
            pas *= 2;
        }
    }
    fout<<setprecision(4)<<fixed<<xnext<<" "<<ynext;
    return 0;
}