Cod sursa(job #1273533)

Utilizator crucerucalinCalin-Cristian Cruceru crucerucalin Data 22 noiembrie 2014 16:54:00
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.78 kb
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cassert>


struct Point
{
    Point()
    : Point(0, 0)
    {
    }

    Point(const Point &other)
    : Point(other.x, other.y)
    {
    }

    Point(int _x, int _y)
    : x(_x)
    , y(_y)
    {
    }

    Point &operator=(const Point &other)
    {
        x = other.x;
        y = other.y;
        return *this;
    }

    int x;
    int y;
};

double euclid_dist(const Point &lhs, const Point &rhs)
{
    return std::sqrt(std::pow(lhs.x - rhs.x, 2) + std::pow(lhs.y - rhs.y, 2));
}

double brute_force_dist(const std::vector<Point> &V)
{
    double curr_min = std::numeric_limits<double>::max();
    for (auto i = 0; i < static_cast<int>(V.size() - 1); ++i)
        for (auto j = i + 1; j < static_cast<int>(V.size()); ++j) {
            double curr_dist = euclid_dist(V[i], V[j]);
            if (curr_dist < curr_min)
                curr_min = curr_dist;
        }

    return curr_min;
}

double min_crossing(const std::vector<Point> &Xl, const std::vector<Point> &Xd,
                    double pos_min)
{
    std::vector<Point> X_sec;

    for (auto it = Xl.crbegin(); it != Xl.crend(); ++it) {
        if (euclid_dist(*it, Xd.front()) > pos_min)
            break;
        X_sec.push_back(*it);
    }

    return brute_force_dist(X_sec);
}


double min_dist(std::vector<Point> &X, std::vector<Point> &Y)
{
    // Same size - mandatory
    assert(X.size() == Y.size());

    // Check end condition
    if (X.size() <= 3)
        return brute_force_dist(X);

    int mid = X.size() / 2;

    // Divide
    std::vector<Point> Xl, Yl, Xd, Yd;
    for (auto &point : X)
        if (point.x < X[mid].x)
            Xl.push_back(point);
        else
            Xd.push_back(point);

    for (auto &point : Y)
        if (point.x < X[mid].x)
            Yl.push_back(point);
        else
            Yd.push_back(point);

    // Conquer
    double pos_min = std::min(min_dist(Xl, Yl), min_dist(Xd, Yd));
    return std::min(pos_min, min_crossing(Xl, Xd, pos_min));
}

struct XCompare : public std::binary_function<Point, Point, bool>
{
    bool operator()(const Point &a, const Point &b)
    {
        return a.x < b.x;
    }
};

struct YCompare : public std::binary_function<Point, Point, bool>
{
    bool operator()(const Point &a, const Point &b)
    {
        return a.y < b.y;
    }
};

int main()
{
    std::ifstream fin("cmap.in");
    std::ofstream fout("cmap.out");

    int N;
    fin >> N;

    std::vector<Point> X_way(N);
    for (auto i = 0; i < N; ++i)
        fin >> X_way[i].x >> X_way[i].y;

    std::vector<Point> Y_way = X_way;

    std::sort(X_way.begin(), X_way.end(), XCompare());
    std::sort(Y_way.begin(), Y_way.end(), YCompare());

    fout << std::fixed << std::setprecision(6) << min_dist(X_way, Y_way);

    return 0;
}