Cod sursa(job #2593563)

Utilizator robert.barbu27robert barbu robert.barbu27 Data 4 aprilie 2020 10:43:27
Problema Adapost 2 Scor 100
Compilator cpp-64 Status done
Runda 7 Marime 1.11 kb

#include <bits/stdc++.h>
#define maxn 155
#define maxt 3505
using namespace std;
ifstream f("adapost2.in");
ofstream g("adapost2.out");
double x[50005],y[50005],sumx,sumy,medx,medy,sol;
int n;
double dx[4]={1,-1,0,0};
double dy[4]={0,0,1,-1};
double dist(double x1,double y1,double x2,double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double tot(double x1,double y1)
{
    double solt=0;
    for(int i=1;i<=n;i++)
    {
        solt+=dist(x1,y1,x[i],y[i]);
    }
    return solt;
}
int main()
{
f>>n;
for(int i=1;i<=n;i++)
{
    f>>x[i]>>y[i];
    sumx+=x[i];
    sumy+=y[i];

}
medx=sumx/(n*1.0);
medy=sumy/(n*1.0);
sol=tot(medx,medy);
for(double  pas=1000;pas>=0.001;pas/=2)
{
    double x=medx;
    double y=medy;
    bool ok=0;

    for(int d=0;d<4;d++)
    {

        double xx=x+dx[d]*pas;
        double yy=y+dy[d]*pas;
        double sum=tot(xx,yy);
        if(sum<sol)
        {
            sol=sum;
            medx=xx;
            medy=yy;
            ok=1;


        }
    }
    if(ok) pas*=2;


}
g<<fixed<<setprecision(3)<<medx<<" "<<medy;
}