Cod sursa(job #843366)

Utilizator danalex97Dan H Alexandru danalex97 Data 27 decembrie 2012 21:16:22
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;

ifstream F("adapost2.in");
ofstream G("adapost2.out");

#define x first
#define y second
typedef pair<double, double> Pair;

const double EPS = 1e-4;
const int Nmax = 50010;

const double dx[4]= { 1 , 0 , -1, 0 };
const double dy[4]= { 0 , -1, 0 , 1 };

int N;
Pair Point,A[Nmax];

double Best;

inline double sqr(double X)
{   return X*X; }

double Dist(const Pair& P)
{
    double Point=0;

    for (int i=1;i<=N;++i)
        Point += sqrt( sqr(P.x-A[i].x) + sqr(P.y-A[i].y) );

    return Point;
}

int main()
{
    F>>N;
    for (int i=1;i<=N;++i)
    {
        F>>A[i].x>>A[i].y;
        Point.x += A[i].x;
        Point.y += A[i].y;
    }

    Point.x /= 1.0*N ;
    Point.y /= 1.0*N ;

    Best = Dist(Point);

    for (double Move=16; Move>EPS; Move/=2.0)
        for (int i=0;i<4;++i)
        {
            Pair Next;

            Next.x = Point.x + Move * dx[i];
            Next.y = Point.y + Move * dy[i];

            double Now = Dist( Next );

            if ( Now < Best )
            {
                Best = Now;
                Point = Next;
                Move *= 2;
                break;
            }
        }

    G<<fixed<<setprecision(4)<<Point.x<<' '<<Point.y<<'\n';
}