Cod sursa(job #1371412)

Utilizator crucerucalinCalin-Cristian Cruceru crucerucalin Data 3 martie 2015 21:20:37
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.62 kb
#include <fstream>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <limits>
#include <cmath>


struct point
{
    int x;
    int y;

    point(int _x, int _y)
    : x(_x)
    , y(_y)
    {}
};

struct x_pred
{
    bool operator()(const point& lhs, const point& rhs)
    {
        return lhs.x < rhs.x;
    }
};

struct y_pred
{
    bool operator()(const point& lhs, const point& rhs)
    {
        return lhs.y < rhs.y;
    }
};

double euclid_dist(const point& lhs, const point& rhs)
{
    return std::sqrt((long long)(lhs.x - rhs.x)*(lhs.x - rhs.x) +
                     (long long)(lhs.y - rhs.y)*(lhs.y - rhs.y));
}

double brute_force_impl(const std::vector<point>& x_points,
                        std::vector<point>& points,
                        int low,
                        int high)
{
    auto min_dist = std::numeric_limits<double>::max();

    for (auto i = low; i < high; ++i)
        for (auto j = i + 1; j <= high; ++j)
            min_dist = std::min(min_dist, euclid_dist(x_points[i], x_points[j]));

    std::sort(points.begin() + low, points.begin() + high + 1, y_pred{});
    return min_dist;
}

double smallest_crossing(const std::vector<point>& y_points,
                         double gamma,
                         const point& ref,
                         int low,
                         int high)
{
    std::vector<point> y_prime;

    for (auto i = low; i <= high; ++i)
        if (y_points[i].x <= ref.x + gamma && y_points[i].x >= ref.x - gamma)
            y_prime.push_back(y_points[i]);

    auto min_dist = std::numeric_limits<double>::max();
    if (y_prime.size() < 2)
        return min_dist;

    for (auto i = 0u; i < y_prime.size() - 1; ++i)
        for (auto j = i + 1; j < y_prime.size() && j - i < 8; ++j)
            min_dist = std::min(min_dist, euclid_dist(y_prime[i], y_prime[j]));

    return min_dist;
}

void merge_points(std::vector<point> &points, int low, int mid, int high)
{
    std::vector<point> aux_points;

    auto i = low, j = mid + 1;
    while (i <= mid && j <= high)
        aux_points.push_back(
                points[i].y < points[j].y ? points[i++] : points[j++]
        );

    while (i <= mid)
        aux_points.push_back(points[i++]);

    while (j <= high)
        aux_points.push_back(points[j++]);

    for (int q = low; q <= high; ++q)
        points[q] = aux_points[q - low];
}

double smallest_dist_impl(const std::vector<point>& x_points,
                          std::vector<point>& points,
                          int low,
                          int high)
{
    if (high - low < 3)
        return brute_force_impl(x_points, points, low, high);

    auto mid = (low + high)/2;
    auto gamma = std::min(
                    smallest_dist_impl(x_points, points, low, mid),
                    smallest_dist_impl(x_points, points, mid + 1, high)
                );
    merge_points(points, low, mid, high);

    return std::min(
            gamma,
            smallest_crossing(points, gamma, x_points[mid], low, high)
    );
}


double smallest_dist(const std::vector<point>& x_points,
                     std::vector<point>& points)
{
    return smallest_dist_impl(x_points, points, 0, x_points.size() - 1);
}

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

    int N;
    fin >> N;

    std::vector<point> points_x;
    for (auto i = 0; i < N; ++i) {
        int x, y;
        fin >> x >> y;
        points_x.emplace_back(x, y);
    }

    std::sort(points_x.begin(), points_x.end(), x_pred{});
    auto points = points_x;

    fout << std::setprecision(6) << std::fixed
         << smallest_dist(points_x, points);
    return 0;
}