Cod sursa(job #1337711)

Utilizator ladpro98Anh Duc Le ladpro98 Data 9 februarie 2015 13:30:06
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <vector>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define SZ(a) (int(a.size()))
#define MP make_pair
#define X first
#define Y second

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const double EPS = 1e-3 / 2;
const double INF = 1e9;

using namespace std;

typedef pair<double, double> point;

void maximize(double &a, double b) {a = a > b ? a : b;}
void minimize(double &a, double b) {a = a > b ? b : a;}

#define sqr(a) ((a) * (a))
double dist(point &a, point &b) {
    return sqrt(sqr(a.X - b.X) + sqr(a.Y - b.Y));
}

double evaluate(point C, vector<point> &a) {
    double sumDist = 0;
    FOR(i, 0, SZ(a)) sumDist += dist(C, a[i]);
    return sumDist;
}

point geometricMedian(vector<point> &a) {
    //simulated annealing
    double x = 0, y = 0;
    point MIN (INF, INF), MAX(-INF, -INF);
    int n = SZ(a);
    FOR(i, 0, n) {
        x += a[i].X; y += a[i].Y;
        minimize(MIN.X, a[i].X);
        minimize(MIN.Y, a[i].Y);
        maximize(MAX.X, a[i].X);
        maximize(MAX.Y, a[i].Y);
    }
    x /= n; y /= n;
    double length = max(MIN.X + MAX.X, MIN.Y + MAX.Y) / 4;
    double answer = evaluate(MP(x, y), a);
    while (length > EPS) {
        bool updated = 0;
        FOR(dir, 0, 4) {
            double newX = x + length * dx[dir];
            double newY = y + length * dy[dir];
            double newAns = evaluate(MP(newX, newY), a);
            if (newAns < answer) {
                answer = newAns;
                x = newX; y = newY;
                updated = 1;
                break;
            }
        }
        if (!updated) length /= 2;
    }
    return MP(x, y);
}

vector<point> a;

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    freopen("adapost2.in", "r", stdin);
    freopen("adapost2.out", "w", stdout);
    int n;
    cin >> n;
    a = vector<point> (n);
    FOR(i, 0, n) cin >> a[i].X >> a[i].Y;
    point median = geometricMedian(a);
    cout << setprecision(4) << fixed << median.X << ' ' << median.Y << endl;
    return 0;
}