Cod sursa(job #2046156)

Utilizator retrogradLucian Bicsi retrograd Data 23 octombrie 2017 15:16:43
Problema Adapost 2 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;
 
double dx[] = {0, 1, 0, -1},
       dy[] = {1, 0, -1, 0};
 
double X[50001], Y[50001];
int I[50001];
int n;
 
 
double dist(double x1, double y1, double x2, double y2) {
    x1 -= x2; y1 -= y2;
    return sqrt(x1*x1 + y1*y1);
}
double calcDist(double x, double y) {
    double d = 0;
    for(int i=1; i<=n; i++)
        d += dist(X[i], Y[i], x, y);
    return d;
}
 
 
int main() {
    freopen("adapost2.in", "r", stdin);
    freopen("adapost2.out", "w", stdout);
 
    cin >> n;
 
    double x = 0, y = 0;
 
    for(int i=1; i<=n; i++) {
        cin >> X[i] >> Y[i];
    }
 
    x /= n;
    y /= n;
 
    double delta = 0;
    for(int i=1; i<=n; i++)
        delta = max(delta, dist(X[i], Y[i], x, y));
 
    double dnow = calcDist(x, y);
 
    for(int it=1; it*n <= 1000000; it++) {
        double dmin = 0; int choose = -1;
 
        for(int d=0; d<4; d++) {
            double dcand = calcDist(x + delta * dx[d], y + delta * dy[d]);
            if(dcand > dnow) continue;
 
            if(choose == -1 || dcand < dmin) {
                dmin = dcand;
                choose = d;
                break;
            }
        }
 
        if(choose != -1)
            x += delta * dx[choose], y += delta * dy[choose], dnow = dmin;
        else delta /= 2;
    }
 
    cout << x << " " << y;
 
    return 0;
}