Cod sursa(job #1068585)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 28 decembrie 2013 15:20:10
Problema Adapost 2 Scor 75
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.42 kb
#include <fstream>
#include <cmath>
using namespace std;
const int Nmax = 50002;
const double dx[] = { 0, 1,  0, -1};
const double dy[] = { 1, 0, -1, 0};
struct Point
{
    double x,y;
};
Point A[Nmax], Sol;
double  best;
int n;
inline double sqr(const double x)
{
    return x * x;
}
inline double Dist(const Point A,const Point B)
{
    return sqrt(sqr(A.x - B.x) + sqr(A.y - B.y));
}
inline double Sum(const Point G)
{
    double sum = 0;
    for(int i = 1;i <= n; ++i)
        sum += Dist(G,A[i]);
    return sum;
}
inline void Read()
{
    int i;
    ifstream f("adapost2.in");
    f >> n;
    for(i = 1;i <= n; ++i)
    {
        f >> A[i].x >> A[i].y;
        Sol.x += A[i].x;
        Sol.y += A[i].y;
    }
    Sol.x /= 1.0*n;
    Sol.y /= 1.0*n;
    best = Sum(Sol);
    f.close();
}

inline void Solve()
{
    int k,i;
    bool ok;
    double x,D = 16;
    Point G;
    for(k = 1;k <= 20; ++k,D /= 2.0)
    {
        ok  = 0;
        for(i = 0;i < 4; ++i)
        {
            G.x = Sol.x + D*dx[i];
            G.y = Sol.y + D*dy[i];
            x = Sum(G);
            if(x < best)
            {
                best = x;
                Sol = G;
                ok = 1;
                break;
            }
        }
        if(ok)
            D *= 2.0;
    }
}

inline void Write()
{
    ofstream g("adapost2.out");
    g << Sol.x <<" "<< Sol.y <<"\n";
    g.close();
}

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