Cod sursa(job #2274280)

Utilizator LucianTLucian Trepteanu LucianT Data 1 noiembrie 2018 17:07:36
Problema Adapost 2 Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <fstream>
#include <cmath>
#define Point pair<double,double>
using namespace std;

const int maxN=5e4+3;
const int maxCoord=1e3;
const double EPS=1e-4;

const int dx[]={-1,0,1,0};
const int dy[]={0,1,0,-1};

int n;
Point v[maxN];
Point centroid,sol;

double getDist(Point a,Point b){
    double difx=a.first-b.first;
    double dify=a.second-b.second;

    return sqrt(difx*difx+dify*dify);
}

double getTotalDist(Point center){
    double res=0;
    for(int i=1;i<=n;i++)
        res+=getDist(center,v[i]);

    return res;
}

int main(){
    ifstream cin("adapost2.in");
    ofstream cout("adapost2.out");

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>v[i].first>>v[i].second;

        centroid.first+=v[i].first;
        centroid.second+=v[i].second;
    }

    centroid.first/=n;
    centroid.second/=n;

    sol=centroid;
    double bestDist=getTotalDist(sol);

    for(double step=maxCoord;step>EPS;){
        Point cand;
        double minDist=1e10;

        for(int i=0;i<4;i++){
            Point curr;
            curr.first=sol.first+step*dx[i];
            curr.second=sol.second+step*dy[i];

            double currentDist=getTotalDist(curr);
            if(currentDist<minDist){
                minDist=currentDist;
                cand=curr;
            }
        }

        if(minDist<bestDist){
            bestDist=minDist;
            sol=cand;
        } else {
            step/=2;
        }
    }

    cout<<sol.first<<" "<<sol.second;

    return 0;
}