Cod sursa(job #1054474)

Utilizator UnforgivenMihai Catalin Botezatu Unforgiven Data 13 decembrie 2013 21:42:33
Problema Adapost 2 Scor 59
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.75 kb
#include <iostream>
#include <fstream>
#include <math.h>

const static int NMAX = 50002;

using namespace std;

class Point
{
public:
    double x, y;
    Point(const double & x = 0, const double & y = 0)
    {
        this->x = x;
        this->y = y;
    }
    double distanceToPoint(const Point & other) const
    {
        return sqrt((x - other.x) * (x - other.x) + (y - other.y) * (y - other.y));
    }
};

ifstream input("adapost2.in");
ofstream output("adapost2.out");
Point puncte[NMAX];
int N;

double sumDist(const Point & point)
{
    double sum = 0;
    for (int i = 0; i < N; i++)
    {
        sum += point.distanceToPoint(puncte[i]);
    }
    return sum;
}

double round(double x)
{
    return floor(x * 10000 + 0.5) / 10000;
}

int main()
{
    Point aux;
    Point punct;
    Point intermediar;

    input >> N ;
    for (int i = 0; i < N ; i++)
    {
        input >> puncte[i].x >> puncte[i].y;
        punct.x += puncte[i].x;
        punct.y += puncte[i].y;
    }

    punct.x /= N;
    punct.y /= N;

    double zecimale = 100;
    int dirx[] = { 0 , 0 , -1 , 1};
    int diry[] = { -1 , 1 , 0 , 0};
    double min_dist = sumDist(punct);

    while (zecimale > 0.0001)
    {
        bool found = false;
        for (int i =0 ; i < 4 && !found; i++)
        {
            intermediar = Point(punct.x + dirx[i] * zecimale , punct.y + diry[i] * zecimale);
            double dist = sumDist(intermediar);
            if (min_dist > dist)
            {
                min_dist = dist;
                aux = intermediar;
                found = true;
            }
        }
        if (found)
        {
            punct = aux;
            aux = Point(0,0);
        }
        zecimale /= 2;
    }

    output << round(punct.x) << " " << round(punct.y) << endl;

    return 0;
}