Cod sursa(job #1061188)

Utilizator mariacMaria Constantin mariac Data 19 decembrie 2013 13:52:42
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.56 kb
#include <fstream>
#include <math.h>

using namespace std;
FILE *f = fopen("adapost2.out", "w");
FILE *fi = fopen("adapost2.in", "r");

int N;
double x[50005], y[50005];
double dmin = 200000000;
double dist(int i, int j)
{
    double xx = x[i]-x[j], yy = y[i] - y[j];
    return sqrt( xx * xx + yy * yy);
}
double suma_dist(double a, double b)
{
    double s = 0;
    x[N + 1] = a; y[N + 1] = b;
    for( int i = 1; i <= N; i++)
        s += dist(i, N+1);
    return s;
}
int main()
{
    int i;
    double sx = 0, sy = 0,abat = 200;

    fscanf( fi,"%d", &N);

    for( i = 1; i <= N; i++)
    {
        fscanf(fi, "%lf %lf", &x[i], &y[i]);
        sx += x[i];
        sy += y[i];
    }
    sx /= N;
    sy /= N;
    while(abat > 0.0005)
    {
        double f;
        f = suma_dist(sx + abat, sy);
        if( f  < dmin)
            {
                dmin = f;
                sx += abat;
                continue;
            }
        f = suma_dist(sx - abat, sy);
        if( f  < dmin)
            {
                dmin = f;
                sx -= abat;
                continue;
            }
        f = suma_dist( sx, sy + abat);
        if( f  < dmin)
            {
                dmin = f;
                sy += abat;
                continue;
            }
        f = suma_dist( sx, sy - abat);
        if( f  < dmin)
            {
                dmin = f;
                sy -= abat;
                continue;
            }
        abat = abat / 2;
    }

    fprintf(f,"%.4f %.4f",sx, sy);

    return 0;
}