Cod sursa(job #2031242)

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

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

typedef pair<double, double> pnt;

pnt pts[DIM];

inline double calcdist(pnt p, int n)
{
    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)
{
    freopen("adapost2.in", "r", stdin);
    freopen("adapost2.out", "w", stdout);
    
    int n;
    scanf("%d", &n);
    
    double sx = 0, sy = 0, stp = 1000.0;
    for (int i = 1; i <= n; ++i) {
        scanf("%lf %lf", &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 <= 30; ++i, stp /= 2.0) {
        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;
    }
    
    printf("%lf %lf\n", cn.first, cn.second);
    return 0;
}