Cod sursa(job #2592682)

Utilizator levladiatorDragutoiu Vlad-Ioan levladiator Data 2 aprilie 2020 02:12:31
Problema Adapost 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("adapost2.in");
ofstream fout("adapost2.out");

int n;
double medx,medy,solpointx,solpointy,soldist;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
struct coord
{
    double x,y;
};
coord v[50005];

double dist(double a,double b,double c,double d)
{
    return sqrt((a-c)*(a-c)+(b-d)*(b-d));
}

double distall(double x,double y)
{
    double sum=0;
    for(int i=1;i<=n;i++)
    {
        sum+=dist(x,y,v[i].x,v[i].y);
    }
    return sum;
}
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>v[i].x>>v[i].y;
        medx+=v[i].x;
        medy+=v[i].y;
    }
    solpointx=medx/n;
    solpointy=medy/n;
    soldist=distall(solpointx,solpointy);

    for(double step=1000;step>=0.001;step/=2)
    {
        double x=solpointx;
        double y=solpointy;
        for(int j=0;j<4;j++)
        {
            double xx=x+dx[j]*step;
            double yy=y+dy[j]*step;
            double auxdist=distall(xx,yy);
            if(auxdist<soldist)
            {
                soldist=auxdist;
                solpointx=xx;
                solpointy=yy;
                step*=2;
            }
        }
    }
    fout<<setprecision(3)<<fixed<<solpointx<<" "<<solpointy;
}