Cod sursa(job #1841807)

Utilizator mariusn01Marius Nicoli mariusn01 Data 6 ianuarie 2017 01:01:52
Problema Adapost 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <cstdio>
#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 () {
    FILE *fin  = fopen("adapost2.in", "r");
    FILE *fout = fopen("adapost2.out", "w");

    fscanf(fin, "%d", &n);
    for (int i=1;i<=n;i++) {
        fscanf(fin, "%lf %lf", &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;
        }
    }
    fprintf(fout,"%.4lf %.4lf", xnext, ynext);
    return 0;
}