Cod sursa(job #603720)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 18 iulie 2011 14:03:57
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <cstdio>
#include <cmath>

using namespace std;

#define maxn 50010
#define inf 1000000000

int n, i, j, k;
double pd, pas, ad, sx, sy, x[maxn], y[maxn];
const int d1[]={0, 0, 1, -1};
const int d2[]={1, -1, 0, 0};

double dist(double x1, double y1, double x2, double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

double sum_dist(double xc, double yc)
{
    ad=0;
    for(int i=1; i<=n; ++i)
        ad+=dist(xc, yc, x[i], y[i]);
    return ad;
}

int main()
{
    freopen("adapost2.in", "r", stdin);
    freopen("adapost2.out", "w", stdout);

    scanf("%d", &n);
    for(int i=1; i<=n; ++i)
        scanf("%lf%lf", &x[i], &y[i]);

    pd=inf;
    pas=512;
    for(int i=1; i<=50; ++i, pas=pas/2)
        for(int j=0; j<4; ++j)
            if(pd>sum_dist(sx+pas*d1[j], sy+pas*d2[j]))
            {
                pd=ad;
                sx+=pas*d1[j];
                sy+=pas*d2[j];
                pas*=2;
                break;
            }

    printf("%.5lf %.5lf\n", sx, sy);

    return 0;
}