Cod sursa(job #2066255)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 14 noiembrie 2017 20:26:37
Problema Adapost 2 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

ifstream fin("adapost2.in");
ofstream fout("adapost2.out");

const ld dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
const ld dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
const int NMax = 5e4 + 50;

ld power(const ld &x) {
    return x * x;
}
ld pointsDistance(const pair < ld, ld > &a, const pair < ld, ld > &b) {
    return sqrtl(power(a.first - b.first) + power(a.second - b.second));
}
ld allDistance(const vector < pair < ld, ld > > &from, const pair < ld, ld > &x) {
    ld ret = (long double)0.0;
    for(const auto &it: from) {
        ret += pointsDistance(it, x);
    }

    return ret;
}

int main() {

    int n;
    fin >> n;

    vector < pair < ld, ld > > points(n);
    for(auto &it: points) fin >> it.first >> it.second;

    pair < ld, ld > ans = points[0];

    int dir = -1;
    pair < ld, ld > auxPair;
    ld auxDist, best;
    ld dist = allDistance(points, ans);

    ld lo = (long double)0.0;
    ld hi = (long double)1000.0;
    while(hi >= (long double)0.00001) {
        dir = -1;
        best = dist;
        for(int d = 0; d < 8; ++d) {
            auxPair = {ans.first + dx[d] * hi, ans.second + dy[d] * hi};
            auxDist = allDistance(points, auxPair);

            if(auxDist < best) {
                best = auxDist;
                dir = d;
            }
        }

        if(dir != -1) {
            ans.first += dx[dir] * hi;
            ans.second += dy[dir] * hi;
        }

        hi /= (long double)2.0;
    }

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