Cod sursa(job #2066386)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 14 noiembrie 2017 22:51:51
Problema Adapost 2 Scor 84
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <bits/stdc++.h>
 
using namespace std;
 
ifstream fin("adapost2.in");
ofstream fout("adapost2.out");
 
typedef pair < double, double > var;
 
const int dx[] = {-1, -1, 1, 1};
const int dy[] = {1, -1, 1, -1};

const int NMax = 5e4 + 50;

var data[NMax];
int n;

double pointDistance(const var &a, const var &b) {
    double x = (a.first - b.first);
    double y = (a.second - b.second);
    return sqrt(x * x + y * y);
}
double allDistance(const var &x) {
    double ret = 0.0;
    for(int i = 0; i < n; ++i) {
        ret += pointDistance(data[i], x);
    }
    return ret;
}
 
int main() {
    fin >> n;
 
    for(int i = 0; i < n; ++i) {
        fin >> data[i].first >> data[i].second;
    }
 
    var ans = {0, 0};
    for(int i = 0; i < n; ++i) {
        ans.first += data[i].first;
        ans.second += data[i].second;
    }
    ans.first /= (double) n;
    ans.second /= (double) n;
 
    double len = allDistance(ans);
 
    double dist = 1000.0;
    while(dist >= 0.0000001) {
        for(int d = 0; d < 4; ++d) {
            var aux = {ans.first + dx[d] * dist, ans.second + dy[d] * dist};
            double sum = allDistance(aux);
 
            if(sum < len) {
                len = sum;
                ans = aux;
            }
        }
 
        dist /= 2.0;
    }
 
    fout << fixed << setprecision(4) << ans.first << " " << ans.second;
    return 0;
}