Cod sursa(job #2294495)

Utilizator Alex18maiAlex Enache Alex18mai Data 2 decembrie 2018 14:58:16
Problema Adapost 2 Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.59 kb
//ALEX ENACHE

#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <time.h>
#include <iomanip>
#include <deque>
#include <math.h>
#include <cmath>
#include <assert.h>
#include <stack>
#include <bitset>
#include <random>
#include <chrono>

using namespace std;

//#include <iostream>

#include <fstream>
ifstream cin ("adapost2.in");ofstream cout ("adapost2.out");

struct nod{
    long double x , y;
};

nod v[50100];

long double dirx[] = {0 , 0 , 1 , -1};
long double diry[] = {1 , -1 , 0 , 0};

int n;

long double dist (long double x , long double y){
    long double sum = 0;
    for (int i=1; i<=n; i++){
        sum += sqrt((x - v[i].x) * (x - v[i].x) + (y - v[i].y) * (y - v[i].y));
    }
    return sum;
}

int main() {

    //freopen("input", "r", stdin);freopen("output", "w", stdout);

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>n;

    for (int i=1; i<=n; i++){
        cin>>v[i].x>>v[i].y;
    }

    long double x = 500;
    long double y = 500;

    long double p = 500;
    long double eps = 0.00001;

    long double MIN = 1e9;

    while (p > eps){
        int ok = 0;
        for (int i=0; i<4; i++){
            long double X = x + dirx[i]*p;
            long double Y = y + diry[i]*p;
            long double d = dist(X , Y);

            if (d < MIN){
                MIN = d;
                x = X;
                y = Y;
                ok = 1;
            }
        }
        if (!ok){
            p /= 2.0;
        }
    }

    cout<<setprecision(10)<<fixed<<x<<" "<<y<<'\n';

    return 0;
}