Cod sursa(job #2045608)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 22 octombrie 2017 16:46:10
Problema Adapost 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include<bits/stdc++.h>
#define maxN 50005
using namespace std;
pair<long double,long double> v[maxN];
int n;
int d[5][5];
inline void Set()
{
    d[1][1]=0;
    d[1][2]=1;
    d[2][1]=0;
    d[2][2]=-1;
    d[3][1]=1;
    d[3][2]=0;
    d[4][1]=-1;
    d[4][2]=0;
}
pair<long double,long double> mp,x;
inline long double Solve(pair<long double,long double> p)
{
    long double s=0;
    for(int i=1;i<=n;i++)
    {
        s=s+(sqrt((long double)(v[i].first-p.first)*(v[i].first-p.first)+(v[i].second-p.second)*(v[i].second-p.second)));
    }
    return s;
}
ifstream fin("adapost2.in");
ofstream fout("adapost2.out");
int main()
{
    Set();
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        //scanf("%lf%lf",&v[i].first,&v[i].second);
        fin>>v[i].first>>v[i].second;
        mp.first+=v[i].first;
        mp.second+=v[i].second;
    }
    mp.first/=n;
    mp.second/=n;
    long double dif=10000;
    long double sol=Solve(mp);

    while(dif>0.0001)
    {
        bool ok=0;
        for(int i=1;i<=4;i++)
        {
            x.first=mp.first+dif*d[i][1];
            x.second=mp.second+dif*d[i][2];
            long double s=Solve(x);
            if(s<sol)
            {
                sol=s;
                ok=1;
                mp=x;
            }
        }
        if(!ok) dif/=2.0;
    }

    fout<<setprecision(4)<<fixed<<mp.first<<' '<<mp.second<<'\n';

    return 0;
}