Cod sursa(job #1060941)

Utilizator poptibiPop Tiberiu poptibi Data 18 decembrie 2013 22:18:04
Problema Adapost 2 Scor 95
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.15 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;

const int NMAX = 50010;
const double EPS = 1e-4;
const int DX[4] = {-1, 0, 0, 1};
const int DY[4] = {0, -1, 1, 0};

int N;
double X[NMAX], Y[NMAX], AnsX, AnsY;

double TotalDist(double PX, double PY)
{
    double Ans = 0;
    for(int i = 1; i <= N; ++ i)
        Ans += sqrt((PX - X[i]) * (PX - X[i]) + (PY - Y[i]) * (PY - Y[i]));
    return Ans;
}

int main()
{
    freopen("adapost2.in", "r", stdin);
    freopen("adapost2.out", "w", stdout);

    scanf("%i", &N);
    for(int i = 1; i <= N; ++ i) scanf("%lf %lf", &X[i], &Y[i]);

    double NowDist = TotalDist(AnsX, AnsY);
    for(double Step = 256; Step > EPS; Step /= 2)
        for(int i = 0; i < 4; ++ i)
        {
            double NX = AnsX + Step * DX[i], NY = AnsY + Step * DY[i];
            double Dist = TotalDist(NX, NY);
            if(Dist < NowDist)
            {
                NowDist = Dist;
                AnsX = NX;
                AnsY = NY;
                Step *= 2;
                break;
            }
        }

    printf("%lf %lf\n", AnsX, AnsY);
}