Cod sursa(job #1101769)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 9 februarie 2014 00:07:56
Problema Adapost 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
// hill climbing

#include <fstream>
#include <cmath>
#include <iostream>
#define EPS 0.0001

using namespace std;

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int NMax = 50010;
struct punct
{
    double x, y;
    punct() {x = y = 0.0;}
    punct(const double x, const double y)
    {
        this -> x = x;
        this -> y = y;
    }
};
punct ans, a[NMax] ;
int n;

void Read()
{
    ifstream f ("adapost2.in");
    f>>n;
    for (int i = 1; i <= n; ++i)
    {
        double x, y; f>>x>>y;
        a[i] = punct(x, y);
    }
    f.close();
}

inline double sqr(const double &x)
{
    return x * x;
}

inline double GetDist(const punct &now)
{
    double ret = 0;
    for (int i = 1; i<=n; ++i)
        ret += sqrt(sqr(now.x-a[i].x)+sqr(now.y-a[i].y));
    return ret;
}

inline void Solve()
{
    punct G, now, cpy;
    for (int i = 1; i<=n; ++i)
        G.x += a[i].x, G.y += a[i].y;
    G.x /= n, G.y /= n;
    now = G;
    double dist = GetDist(G);
    for (double ratio = 128.0; ratio >= EPS; ratio /= 2)
    {
        bool modif = false;
        for (int k = 0; k < 4; ++k)
        {
            now.x = G.x + dx[k]*ratio;
            now.y = G.y + dy[k]*ratio;
            double distnow = GetDist(now);
            if (distnow < dist)
            {
                modif = true;
                dist = distnow;
                G = now;
            }
        }
        if (modif)
        {
            ratio *= 2;
        }
    }
    ans = G;
}

void Write()
{
    freopen("adapost2.out", "w", stdout);
    printf("%.4lf %.4lf\n", ans.x, ans.y);
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}