Cod sursa(job #795283)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 7 octombrie 2012 23:19:42
Problema Adapost 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
#include <cmath>
#include <iomanip>
#define NM 50010
#define x first
#define y second

using namespace std;

ifstream f("adapost2.in");
ofstream g("adapost2.out");

typedef pair<double, double> PI;
const double EPS=1e-4;
const double dx[4]={1,0,-1,0};
const double dy[4]={0,-1,0,1};

int N,i,j;
PI ANS,V[NM];
PI NP;
double CANS;
double Move;
double Now;

double Dist (const PI& P)
{
    double ANS=0;
    for (int i=1; i<=N; i++)
        ANS+=sqrt((P.x-V[i].x)*(P.x-V[i].x)+(P.y-V[i].y)*(P.y-V[i].y));

    return ANS;
}

int main ()
{
    f >> N;
    for (i=1; i<=N; i++)
    {
        f >> V[i].x >> V[i].y;
        ANS.x+=V[i].x;
        ANS.y+=V[i].y;
    }

    ANS.x/=1.0*N;
    ANS.y/=1.0*N;
    CANS=Dist(ANS);

    for (Move=1024; Move>EPS; Move/=2.0)
        for (int d=0; d<4; d++)
        {
            NP.x=ANS.x+Move*dx[d];
            NP.y=ANS.y+Move*dy[d];

            Now=Dist(NP);
            if (Now<CANS)
            {
                CANS=Now;
                ANS=NP;
                Move*=2;
                break;
            }
        }

    g << fixed << setprecision(4) << ANS.x << ' ' << ANS.y << '\n';

    f.close();
    g.close();
    return 0;
}