Cod sursa(job #235426)

Utilizator Mishu91Andrei Misarca Mishu91 Data 23 decembrie 2008 21:17:55
Problema Adapost 2 Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <cstdio>
#include <cmath>

#define MAX_N 50005
#define eps 0.0001

const int dx[] = {1, 0, 0,-1},
          dy[] = {0, 1,-1, 0};

struct punct{double x, y;} A[MAX_N];
int N;

double dist(punct p)
{
    double Rez = 0.0;
    for(int i = 1; i <= N; ++i)
        Rez += sqrt((p.x - A[i].x)*(p.x - A[i].x)+(p.y - A[i].y)*(p.y - A[i].y));
    return Rez;
}

void citire()
{
    scanf("%d", &N);

    for(int i = 1; i <= N; ++i)
        scanf("%lf %lf", &A[i].x, &A[i].y);
}

void solve()
{
    double err = 1000.0, D = 1000000.0, dst = 0.0;
    punct p, paux;
    p.x = p.y = 0.0;

    while(err > eps)
    {
        bool ok = true;
        while(ok)
        {
            ok = false;

            for(int k = 0; k < 4; ++k)
            {
                paux.x = p.x + (double)(err * dx[k]),
                paux.y = p.y + (double)(err * dy[k]),
                dst = dist(paux);
                if(D > dst)
                    ok = true,
                    D = dst,
                    p = paux;
            }
        }
        err /= 10;
    }

    printf("%lf %lf\n",p.x, p.y);
}

int main()
{
    freopen("adapost2.in","rt",stdin);
    freopen("adapost2.out","wt",stdout);

    citire();
    solve();
}