Cod sursa(job #1086436)

Utilizator laurionLaurentiu Ion laurion Data 18 ianuarie 2014 02:59:18
Problema Adapost 2 Scor 95
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.01 kb
#define nume "adapost2"
//
#include<stdio.h>
#include<math.h>
#define eps 0.0001
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
struct point
{
    double x,y;
};
int n,ok;
double d;
point p,p2;
point v[50005];

double dist_p(point a, point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double dist(point p)
{
    int i;
    double sol=0.0;
    for(i=1;i<=n;++i)
        sol+=dist_p(p,v[i]);
    return sol;
}

int main()
{
    freopen("adapost2.in", "r", stdin);
    freopen("adapost2.out", "w", stdout);
    scanf("%d",&n);
    int i;
    for(i=1;i<=n;++i)
        scanf("%lf %lf",&v[i].x,&v[i].y);
    d=dist(p);
    double pas=1<<9;
    while(pas>eps)
    {
        ok=0;
        for(i=0;i<=3;i++)
        {
            p2.x=p.x+dx[i]*pas;
            p2.y=p.y+dy[i]*pas;
            if(d>dist(p2))
            {
                p=p2;
                d=dist(p);
                ok=1;
                break;
            }
        }
        if(ok==0)
            pas/=2;
    }
    printf("%lf %lf",p.x,p.y);
    return 0;
}