Cod sursa(job #918152)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 18 martie 2013 17:46:02
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 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';
}