Cod sursa(job #1457913)

Utilizator sebinechitasebi nechita sebinechita Data 4 iulie 2015 21:08:39
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.28 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream fin("adapost2.in");
ofstream fout("adapost2.out");
#define MAX 50011
#define eps 1e-3
typedef double ld;

pair<ld, ld> a[MAX];
int n;

ld dir[4][2] = { { 0.0, 1.0 } , { 1.0, 0.0 } , { 0.0, -1.0 } , { -1.0, 0.0 } };

ld dist(ld x, ld y)
{
    ld d = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        d += 1.0 * sqrt((a[i].first - x) * (a[i].first - x) + (a[i].second - y) * (a[i].second - y));
    }
    return d;
}

int main()
{
    ld x, y, pas, d1, d, ax, ay;
    int i;
    fin >> n;
    for(i = 1 ; i <= n ; i++)
    {
        fin >> a[i].first >> a[i].second;
        x += a[i].first;
        y += a[i].second;
    }

    x /= n;
    y /= n;
    pas = 50.0;
    while(pas > eps)
    {
        d = dist(x, y);
        int modif = 0;
        for(int k = 0 ; k < 4 ; k++)
        {
            ax = x + pas * dir[k][0];
            ay = y + pas * dir[k][1];
            d1 = dist(ax, ay);
            if(d1 < d)
            {
                x = ax;
                y = ay;
                d = d1;
                modif = 1;
            }
        }
        if(modif == 0)
            pas /= 2;
    }
    fout << x << " " << y << "\n";
}