Cod sursa(job #1062085)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 20 decembrie 2013 18:09:38
Problema Adapost 2 Scor 95
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 0.96 kb
#include<fstream>
#include<cmath>
using namespace std;
const int NMAX = 50005;
int i,j,N; int Dx[]={-1,0,0,1}; int Dy[]={0,-1,1,0};
double L,SolX,SolY,Best,X[NMAX],Y[NMAX],NewX,NewY,Cost;
double Dist(double A,double B,double C,double D)
{
    return sqrt((A-C)*(A-C)+(B-D)*(B-D));
}
int main()
{
    ifstream fin("adapost2.in");
    ofstream fout("adapost2.out");
    fin>>N;
    for(i=1;i<=N;i++)
    {
        fin>>X[i]>>Y[i];
        SolX+=X[i]; SolY+=Y[i];
    }
    SolX/=N; SolY/=N;
    for(i=1;i<=N;i++) Best+=Dist(X[i],Y[i],SolX,SolY);
    for(L=250;L>0.0001;L/=2)
        for(i=0;i<4;i++)
        {
            NewX=SolX+L*Dx[i]; NewY=SolY+L*Dy[i]; Cost=0;
            for(j=1;j<=N;j++) Cost+=Dist(X[j],Y[j],NewX,NewY);
            if(Cost<Best)
            {
                Best=Cost; SolX=NewX; SolY=NewY;
                L*=2; break;
            }
        }
    fout<<SolX<<" "<<SolY<<'\n';
    fin.close(); fout.close();
    return 0;
}