Cod sursa(job #1183402)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 8 mai 2014 23:03:37
Problema Adapost 2 Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <fstream>
#include <iomanip>
#include <cmath>

using namespace std;

struct punct
{
    double x;
    double y;
}v[50005];

punct make_punct(double x,double y)
{
    punct aux;
    aux.x=x;
    aux.y=y;

    return aux;
}

inline double dist(punct a,punct b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

int n;
inline double tot(punct a)
{
    int i;

    double s=0;
    for(i=1;i<=n;i++)
        s+=dist(a,v[i]);
    return s;
}

#define eps 0.001

int main()
{
    ios_base::sync_with_stdio(false);
    ifstream cin("adapost2.in");
    ofstream cout("adapost2.out");

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

    int i;

    cin>>n;
    for(i=1;i<=n;i++)
        cin>>v[i].x>>v[i].y;

    double d=1000;
    punct a;

    a.x=a.y=0;
    for(i=1;i<=n;i++)
        a.x+=v[i].x,a.y+=v[i].y;

    a.x/=n;
    a.y/=n;

    bool ok;
    punct aux;

    while(d>=eps)
    {
        ok=true;
        for(i=0;i<4;i++)
        {
            aux=make_punct(a.x+d*dx[i],a.y+d*dy[i]);
            if(tot(aux)<tot(a))
            {
                a=aux;
                ok=false;
                break;
            }
        }

        if(ok)
            d/=2;
    }

    cout<<fixed<<setprecision(4)<<a.x<<' '<<a.y<<'\n';

    cin.close();
    cout.close();
    return 0;
}