Cod sursa(job #1007628)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 9 octombrie 2013 13:01:35
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <iostream>
#include <fstream>
#include <cmath>
#define NMax 50010
#define EPS 0.0001

using namespace std;

int n;
struct Punct
{
    double x, y;
};
Punct pointbest, a[NMax];
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

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

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

double Dist(const Punct pct)
{
    int i;
    double ret = 0.0;
    for (i=1; i<=n; ++i)
        ret += sqrt(sqr(a[i].x - pct.x) + sqr(a[i].y - pct.y));
    return ret;
}

void Solve()
{
    pointbest.x /= (1.0 * n);
    pointbest.y /= (1.0 * n);
    Punct pointnow;
    double distbest, distnow, value;
    bool ok;

    distbest = Dist(pointbest);
    for (value = 100; value > EPS; value /= 2.0)
    {
        ok = false;
        for (int k = 0; k<4 && !ok; ++k)
        {
            pointnow.x = pointbest.x + value*dx[k];
            pointnow.y = pointbest.y + value*dy[k];
            distnow = Dist(pointnow);
            if (distnow < distbest)
            {
                distbest = distnow;
                pointbest = pointnow;
                ok = true;
            }
        }
        if (ok)
            value *= 2.0;
    }
}

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

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