Cod sursa(job #1273549)

Utilizator crucerucalinCalin-Cristian Cruceru crucerucalin Data 22 noiembrie 2014 17:27:05
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.82 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(long long _x, long long _y)
    : x(_x)
    , y(_y)
    {
    }

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

    long long x;
    long long y;
};

long long euclid_dist(const Point &lhs, const Point &rhs)
{
    return (lhs.x - rhs.x) * (lhs.x - rhs.x) + (lhs.y - rhs.y) * (lhs.y - rhs.y);
}

long long brute_force_dist(const std::vector<Point> &V)
{
    long long curr_min = std::numeric_limits<long long>::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) {
            long long curr_dist = euclid_dist(V[i], V[j]);
            if (curr_dist < curr_min)
                curr_min = curr_dist;
        }

    return curr_min;
}

long long min_crossing(const std::vector<Point> &Xl, const std::vector<Point> &Xd)
{
    long curr_min = std::numeric_limits<long long>::max();

    for (auto it = Xl.crbegin(); it != Xl.crend(); ++it) {
        long long curr_dist = euclid_dist(Xd.front(), *it);
        if (curr_dist < curr_min)
            curr_min = curr_dist;
    }

    return curr_min;
}

long long 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
    return std::min(std::min(min_dist(Xl, Yl), min_dist(Xd, Yd)),
                    min_crossing(Xl, Xd));
}

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) << std::sqrt(min_dist(X_way, Y_way));

    return 0;
}