Cod sursa(job #1233881)

Utilizator assa98Andrei Stanciu assa98 Data 26 septembrie 2014 11:28:51
Problema Adapost 2 Scor 91
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <fstream>
#include <cmath>
#include <algorithm>

#define pe pair<double, double>
#define mp make_pair
#define fi first
#define se second

using namespace std;

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

const int MAX_N = 50100;

int n;
pe v[MAX_N];

double dist(pe a, pe b) {
    return sqrt((a.fi - b.fi) * (a.fi - b.fi) + (a.se - b.se) * (a.se - b.se));
}

double F(pe x) {
    double ans = 0;
    for(int  i = 1; i <= n; i++) {
        ans += dist(x, v[i]);
    }
    return ans;
}

int main() {
    fin >> n;
    for(int i = 1; i <= n; i++) {
        fin >> v[i].fi >> v[i].se;
    }
    
    pe poz = mp(0, 0);
    double ans = F(poz);
    double d = 1024.0;
    for(int i = 1; i <= 40; i++) {
        double a = F(mp(poz.fi, poz.se + d));
        if(a < ans) {
            poz = mp(poz.fi, poz.se + d);
            ans = a;
            continue;
        }
        
        a = F(mp(poz.fi, poz.se - d));
        if(a <= ans) {
            poz = mp(poz.fi, poz.se - d);
            ans = a;
            continue;
        }
        
        a = F(mp(poz.fi + d, poz.se));
        if(a < ans) {
            poz = mp(poz.fi + d, poz.se);
            ans = a;
            continue;
        }
        
        a = F(mp(poz.fi - d, poz.se));
        if(a < ans) {
            poz = mp(poz.fi - d, poz.se);
            ans = a;
            continue;
        }

        d /= 2.0;
    }

    fout << poz.fi << ' ' << poz.se;

    return 0;
}