Cod sursa(job #2066383)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 14 noiembrie 2017 22:42:01
Problema Adapost 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 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, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
 
double power(const double &x) {
    return x * x;
}
double pointDistance(const var &a, const var &b) {
    return sqrt(power(a.first - b.first) + power(a.second - b.second));
}
double allDistance(const vector < var > &data, const var &x) {
    double ret = 0.0;
    for(auto it: data) {
        ret += pointDistance(it, x);
    }
    return ret;
}
 
int main() {
    int n;
    fin >> n;
 
    vector < var > data(n);
    for(auto &it: data) {
        fin >> it.first >> it.second;
    }    
 
    var ans = {0, 0};
    for(auto it: data) {
        ans.first += it.first;
        ans.second += it.second;
    }
    ans.first /= (double) n;
    ans.second /= (double) n;
 
    double len = allDistance(data, ans);
 
    bool flag = true;
    double dist = 1000.0;
    while(dist >= 0.0000001) {
        flag = false;
        for(int d = 0; d < 4; ++d) {
            var aux = {ans.first + dx[d] * dist, ans.second + dy[d] * dist};
            double sum = allDistance(data, aux);
 
            if(sum < len) {
                len = sum;
                ans = aux;
                flag = true;
            }
        }
 
        if(!flag) dist /= 2.0;
    }
 
    fout << fixed << setprecision(4) << ans.first << " " << ans.second;
    return 0;
}