Cod sursa(job #809314)

Utilizator psycho21rAbabab psycho21r Data 8 noiembrie 2012 09:22:53
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.63 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

const long long INF = 4e18;

struct point
{
    int x, y;
    point(int abscissa, int ordinate)
    {
        x = abscissa;
        y = ordinate;
    }
    friend bool operator< (point a, point b);
};

bool operator< (point a, point b)
{
    if(a.x < b.x)
        return true;
    if(a.x == b.x)
        return a.y < b.y;
    return false;
}

bool is_below(point a, point b)
{
    if(a.y < b.y)
        return true;
    if(a.y == b.y)
        return (a.x < b.x);
    return false;
}

point make_point(int abscissa, int ordinate)
{
    point p(abscissa, ordinate);
    return p;
}

long long distance_squared(point a, point b)
{
    return (b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y);
}

struct plane
{
    private:
        vector<point> points;
        vector<point> y_order_points;
    public:
        void push_point(int abscissa, int ordinate)
        {
            points.push_back(make_point(abscissa, ordinate));
        }
        float distance_between_closest_points()
        {
            sort(points.begin(), points.end());
            y_order_points = points;
            return sqrt(cmap(0, points.size()));
        }
    private:
        long long cmap(int left, int right)
        {
            if(right - left <= 1)
                return INF;
            if(right - left == 2)
            {
                if(is_below(y_order_points[left + 1], y_order_points[left]))
                    swap(y_order_points[left], y_order_points[left + 1]);
                return distance_squared(points[left], points[left + 1]);
            }
            int mid = (left + right)/2;
            long long best = min(cmap(left, mid), cmap(mid, right));

            sort(y_order_points.begin() + left, y_order_points.begin() + right, is_below);

            vector<point> v;
            for(int i = left; i < right; ++i)
                if(abs(y_order_points[i].x - points[mid].x) <= best)
                    v.push_back(y_order_points[i]);
            for(int i = 0; i < v.size(); ++i)
                for(int j = i + 1; j < v.size() && j - i < 8; ++j)
                    best = min(best, distance_squared(v[i], v[j]));
            return best;
        }
};

int main()
{
    ifstream in("cmap.in");
    ofstream out("cmap.out");
    int N;
    in >> N;
    plane P;
    for(int i = 0, x, y; i < N; ++i)
    {
        in >> x >> y;
        P.push_point(x, y);
    }
    out << fixed << P.distance_between_closest_points();
    in.close();
    out.close();
    return 0;
}