Cod sursa(job #2031239)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 2 octombrie 2017 21:26:24
Problema Adapost 2 Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <bits/stdc++.h>
using namespace std;

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

const int DIM = 50005;
const int dx[5] = {0, -1, 0, 1, 0};
const int dy[5] = {0, 0, 1, 0, -1};

typedef pair<long double, long double> pnt;

pnt pts[DIM];

inline long double calcdist(pnt p, int n)
{
    long double sum = 0;
    
    for (int i = 1; i <= n; ++i)
        sum += hypot(abs(p.first - pts[i].first),
                     abs(p.second - pts[i].second));
    
    return sum;
}

int main(void)
{
    int n;
    in >> n;
    
    long double sx = 0, sy = 0, stp = 1000.0;
    for (int i = 1; i <= n; ++i)
        in >> pts[i].first >> pts[i].second,
        sx += pts[i].first, sy += pts[i].second;
    
    pnt cn = {sx / n, sy / n};
    for (int i = 1; i <= 20; ++i, stp /= 2.0) {
        long double dst1 = calcdist(cn, n);
        bool ok = false;
        
        for (int j = 1; j <= 4; ++j) {
            pnt np(cn.first + dx[j] * stp,
                   cn.second + dy[j] * stp);
            
            if (dst1 > calcdist(np, n))
                cn = np, ok = true;
        }
        
        if (ok)
            --i, stp *= 2.0;
    }
    
    out << setprecision(12) << fixed << cn.first << " " << cn.second << endl;
    return 0;
}