Cod sursa(job #196451)

Utilizator DastasIonescu Vlad Dastas Data 26 iunie 2008 16:15:09
Problema Adapost 2 Scor 97
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <cstdio>
#include <cmath>

const int maxn = 50001;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const double eps = 0.0001;

FILE *in = fopen("adapost2.in","r"), *out = fopen("adapost2.out","w");

struct punct
{
    double x, y;
};

int n;
punct a[maxn];
double x, y;

double dist(double x, double y)
{
    double ret = 0;

    for ( int i = 1; i <= n; ++i )
    {
        double dx = a[i].x - x;
        double dy = a[i].y - y;

        ret += sqrt(dx*dx + dy*dy);
    }

    return ret;
}

void read()
{
    fscanf(in, "%d", &n);

    for ( int i = 1; i <= n; ++i )
        fscanf(in, "%lf %lf", &a[i].x, &a[i].y),
        x += a[i].x,
        y += a[i].y;

    x /= n;
    y /= n;
}

void go()
{
    double d = dist(x, y);
    double step = 100.0;

    while ( step > eps )
    {
        for ( int i = 0; i < 4; ++i )
        {
            double nx = (double)x + step*dx[i];
            double ny = (double)y + step*dy[i];

            double t = dist(nx, ny);

            if ( t < d )
            {
                d = t;
                x = nx;
                y = ny;
            }
        }

        step /= 2;
    }
}

int main()
{
    read();
    go();

    fprintf(out, "%.4lf %.4lf\n", x, y);

    return 0;
}