Cod sursa(job #1094606)

Utilizator lianaliana tucar liana Data 29 ianuarie 2014 17:16:40
Problema Adapost 2 Scor 42
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include<stdio.h>
#include<cmath>
#define nmax 50005
#define eps 0.0001
struct punct{ double x, y;};
punct v[nmax];
float dac, drez, dif;
punct rez, rezac;
int i, n, d;
bool sch;
int vx[5]={0,-1,0,0,1};
int vy[5]={0,0,-1,1,0};


void calc()
{
    dac=0;
    for (i=1;i<=n;i++)
        dac+=sqrt((v[i].x-rezac.x)*(v[i].x-rezac.x) + (v[i].y-rezac.y)*(v[i].y-rezac.y));
}
int main()
{
    freopen("adapost2.in","r",stdin);
    freopen("adapost2.out","w",stdout);
    scanf("%ld",&n);
    for (i=1;i<=n;i++)
    {
        scanf("%lf %lf",&v[i].x,&v[i].y);
        rez.x+=v[i].x; rez.y+=v[i].y;
    }
    rez.x/=n;  rez.y/=n;
    rezac=rez;  calc(); drez=dac;
    for (dif=100;dif/=2;dif>=eps)
    {
        sch=1;
        while (sch)
        {
            sch=0;
            for (d=1;d<=4;d++)
            {
                rezac.x=rez.x + dif*vx[d];
                rezac.y=rez.y + dif*vy[d];
                calc();
                if (dac<drez)
                {
                    drez=dac;   rez=rezac;
                    sch=1;
                }
            }
        }
    }
    printf("%.4lf %.4lf",rez.x,rez.y);
    return 0;
}