Cod sursa(job #2066374)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 14 noiembrie 2017 22:28:20
Problema Adapost 2 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 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;
}

double obt[4];

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);

    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};
            obt[d] = allDistance(data, aux);
        }

        double m = obt[0];
        int p = 0;
        for(int d = 1; d < 4; ++d) {
            if(obt[d] < m) {
                m = obt[d];
                p = d;
            }
        }

        if(m < len) {
            len = m;
            ans = {ans.first + dx[p] * dist, ans.second + dy[p] * dist};
        } else {
            dist /= 2.0;
        }
    }

    fout << fixed << setprecision(4) << ans.first << " " << ans.second;
	return 0;
}