Cod sursa(job #1107715)

Utilizator andrettiAndretti Naiden andretti Data 14 februarie 2014 10:29:21
Problema Adapost 2 Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<stdio.h>
#include<algorithm>
#include<cmath>
#define maxn 50005
#define eps 0.001
using namespace std;

struct point{double x,y;} a[maxn],sol;
int n;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
double cost;

double get_cost(point b)
{
    double c=0;
    for(int i=1;i<=n;i++)
     c+=sqrt((b.x-a[i].x)*(b.x-a[i].x)+(b.y-a[i].y)*(b.y-a[i].y));
    return c;
}

void read()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
     scanf("%lf %lf",&a[i].x,&a[i].y),sol.x+=a[i].x,sol.y+=a[i].y;

    sol.x/=n; sol.y/=n; cost=get_cost(sol);
}

void solve()
{
    double c;
    point p;
    int ok;
    for(double i=1000;i>=eps;i/=2)
    {
        ok=0;
        for(int k=0;k<4;k++)
        {
            p.x=sol.x+i*dx[k]; p.y=sol.y+i*dy[k];
            c=get_cost(p); if(c<cost) cost=c,sol=p,ok=1;
            if(ok) i*=2;
        }
    }
}

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

    read();
    solve();
    printf("%lf %lf",sol.x,sol.y);

    fclose(stdin);
    fclose(stdout);
    return 0;
}