Cod sursa(job #3232618)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 31 mai 2024 16:50:49
Problema Adapost 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 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.001;
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;
    int done = 0;
    while ( step > eps )
    {
        done = 0;
        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;
                done = 1;
                break;
            }
        }
        if ( !done )
            step /= 2;
    }
}
int main()
{
    read();
    go();
    fprintf(out, "%.4lf %.4lf\n", x, y);
    return 0;
}