Cod sursa(job #1373435)

Utilizator dinuandAndrei-Mario Dinu dinuand Data 4 martie 2015 18:44:06
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 2.24 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

#define INF ((1 << 30) * 1LL);

struct point {
    int x;
    int y;

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

struct comp_x {
    bool operator() (const point& lp, const point& rp)
    {
        return (lp.x == rp.x) 
                ? lp.y < rp.y 
                : lp.x < rp.x;
    }
};

double euclid_dist(const point& lp, const point& rp)
{
    return sqrt(1LL * (lp.x - rp.x) * (lp.x - rp.x) +
                1LL * (lp.y - rp.y) * (lp.y - rp.y));
}

double min_dist_impl(const vector<point>& points_x, 
                     int left,
                     int right)
{
    if (left == right) /* only one point left */
        return INF;
    if (left + 1 == right) /* two points left in the set */
        return euclid_dist(points_x[left], points_x[right]);

    auto middle = left + (right - left) / 2;
    auto delta = min(
                   min_dist_impl(points_x, left, middle), /* left side */
                   min_dist_impl(points_x, middle + 1, right) /* right side */
                );

    vector<point> points_y;
    for (auto i = left; i <= right; i++) {
        if (max(
             points_x[i].x - points_x[middle].x,
             points_x[middle].x - points_x[i].x
               ) < delta) {
            points_y.emplace_back(points_x[i]);
        } 
    }

    for (auto i = 0; i < points_y.size(); i++) {
        for (auto j = i + 1; j < points_y.size() && j - i < 7; j++) {
            if (euclid_dist(points_y[i], points_y[j]) > 0 &&
                euclid_dist(points_y[i], points_y[j]) < delta) {
                delta = euclid_dist(points_y[i], points_y[j]);
            }
        }
    }

    return delta;

}

double min_dist(const vector<point>& points_x)
{
    return min_dist_impl(points_x, 0, points_x.size() - 1);
}

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

    int N;
    fin >> N;

    vector<point> points_x; /* points sorted by x coordinate */
    for (auto i = 1; i <= N; i++) {
        int x, y;
        fin >> x >> y;
        points_x.emplace_back(x, y);
    }

    sort(points_x.begin(), points_x.end(), comp_x{});

    fout << setprecision(6) << fixed << min_dist(points_x);

    return 0;
}