Cod sursa(job #1457907)

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

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

ld dist(int x, int y)
{
    ld d = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        d += 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, d3, d2, d4, minimum;
    int i;
    fin >> n;
    for(i = 1 ; i <= n ; i++)
        fin >> a[i].first >> a[i].second;
    x = 500;
    y = 500;
    pas = 500;
    while(2 * pas > eps)
    {


        minimum = 0;
        int l = 0;
        while(l < 2)
        {
            l ++;
            d = dist(x, y);
            d1 = dist(x - pas, y);
            d2 = dist(x, y + pas);
            d3 = dist(x + pas, y);
            d4 = dist(x, y - pas);
            minimum = min(d, min(d1, min(d2, min(d3, d4))));
            if(minimum == d1)
                x -= pas;
            else if(minimum == d2)
                y += pas;
            else if(minimum == d3)
                x += pas;
            else if(minimum == d4)
                y -= pas;
            else
                break;
        }
        pas = pas / 2;
    }
    fout << setprecision(3) << fixed << x << " " << y << "\n";
}