Cod sursa(job #2243219)

Utilizator LucaSeriSeritan Luca LucaSeri Data 20 septembrie 2018 09:55:01
Problema Adapost 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <bits/stdc++.h>


using namespace std;

const int MAXN = 50010;

using Point = pair< double, double >;

double dx[] = {1, 1, 1, -1, -1, -1, 0, 0};
double dy[] = {1, 0, -1, 1, 0, -1, 1, -1};

Point p[MAXN];
int n;

double dist(Point cur) {
    double ret = 0;
    for(int i = 0; i < n; ++i) {
        ret += sqrt((cur.first - p[i].first)*(cur.first - p[i].first) + (cur.second - p[i].second)*(cur.second - p[i].second));
    }

    return ret;
}

int main () {
    ifstream f("flux.in");
    ofstream g("flux.out");

    f >> n;
    for(int i = 0; i < n; ++i) f >> p[i].first >> p[i].second;
    Point cur(500, 500);
    double best = dist(cur);
    double len = 500;

    for(int s = 20; s; --s) {
        for(int i = 0; i < 8; ++i) {
            Point now(cur.first + dx[i]*len, cur.second + dy[i]*len);
            double d = dist(now);
            if(d < best) {
                best = d;
                cur = now;
            }
        }
        len /= 2.0;
    }

    g.precision(10);
    g << fixed << cur.first << ' ' << cur.second;
    return 0;
}