Cod sursa(job #2274282)

Utilizator LucianTLucian Trepteanu LucianT Data 1 noiembrie 2018 17:13:01
Problema Adapost 2 Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <cstdio>
#include <utility>
#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(){
    freopen("adapost2.in","r",stdin);
    freopen("adapost2.out","w",stdout);

    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lf %lf",&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;
        }
    }

    printf("%.5lf %.5lf",sol.first,sol.second);

    return 0;
}