Cod sursa(job #1083719)

Utilizator Aleks10FMI - Petrache Alex Aleks10 Data 16 ianuarie 2014 12:28:23
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;
int dx[]={-1,0,0,1}; int dy[]={0,-1,1,0};
int n,i,j;
double solx,soly,x[50001],y[50001],nx,ny,best,k,cost;

double dist(double A, double B, double C, double D){
    return sqrt((A-C)*(A-C)+(B-D)*(B-D));
}
int main()
{
    ifstream f("adapost2.in");
    ofstream g("adapost2.out");
    f>>n;
    for(i=1;i<=n;i++){
        f>>x[i]>>y[i];
        solx+=x[i];
        soly+=y[i];
    }

    solx=solx/n;
    soly=soly/n;
    for(i=1;i<=n;i++)
        best+=dist(x[i],y[i],solx,soly);
    for(k=100;k>0.0001;k=k/2){
        for(i=0;i<4;i++){
            nx=solx+k*dx[i];
            ny=soly+k*dy[i];
            cost=0;
            for(j=1;j<=n;j++)
                cost+=dist(x[j],y[j],nx,ny);
            if(cost<best){
                best=cost;
                solx=nx;
                soly=ny;
                k*=2;
                break;
            }
        }
    }
    g<<solx<<" "<<soly<<'\n';
    return 0;
}