Cod sursa(job #2243233)

Utilizator LucaSeriSeritan Luca LucaSeri Data 20 septembrie 2018 10:06:50
Problema Adapost 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 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;

}