Cod sursa(job #2275897)

Utilizator stefzahZaharia Stefan Tudor stefzah Data 3 noiembrie 2018 18:49:32
Problema Adapost 2 Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <fstream>
#include <math.h>
#include <iomanip>
using namespace std;
ifstream fin("adapost2.in");
ofstream fout("adapost2.out");
int n;
struct punct
{
    double x, y;
} a[50005];
double CalcDist(double X,double Y)
{
    int i;
    double sum=0;
    for(i=1; i<=n; i++)
        sum+=sqrt((a[i].x-X)*(a[i].x-X)+(a[i].y-Y)*(a[i].y-Y));
    return sum;
}
int d1[4]= {0,0,-1,1};
int d2[4]= {-1,1,0,0};
double X,Y;
int main()
{
    int i,j,ok;
    double k,p1,p2,mn;
    fin>>n;
    for(i = 1; i <= n; i++)
    {
        fin>>a[i].x>>a[i].y;
        X+=a[i].x;
        Y+=a[i].y;
    }
    X/=n;
    Y/=n;
    mn=CalcDist(X,Y);
    k=1000;
    while(k>0.0001)
    {
        ok=0;
        for(i=0; i<4; i++)
        {
            p1=X+k*d1[i];
            p2=Y+k*d2[i];
            if(mn>CalcDist(p1,p2))
            {
                mn=CalcDist(p1,p2);
                ok=1;
                X=p1;
                Y=p2;
            }
        }
        if(ok==0)k/=2.0;
    }
    fout<<setprecision(4)<<fixed<<X<<" "<<setprecision(4)<<fixed<<Y<<"\n";
}