Cod sursa(job #2243361)

Utilizator LucaSeriSeritan Luca LucaSeri Data 20 septembrie 2018 12:49:47
Problema Adapost 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 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 () {
    freopen("adapost2.in", "r", stdin);
    freopen("adapost2.out", "w", stdout);


    scanf("%d", &n);
    for(int i = 0; i < n; ++i) scanf("%f%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;
    }



    printf("%.6f %.6f", cur.first, cur.second);
    return 0;
}