Cod sursa(job #809520)

Utilizator psycho21rAbabab psycho21r Data 8 noiembrie 2012 17:05:03
Problema Cele mai apropiate puncte din plan Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 3.1 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

const long long INF = 4e18;

struct point
{
    int x, y;
    point(int abscissa, int ordinate)
    {
        x = abscissa;
        y = ordinate;
    }
    point()
    {
        x = 0;
        y = 0;
    }
    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 ((long long)(b.x - a.x))*((long long)(b.x - a.x)) + ((long long)(b.y - a.y))*((long long)(b.y - a.y));
}
struct plane
{
    private:
        vector<point> points;
        vector<point> y_order_points;
        vector<point> temp;
        vector<point> v;
    public:
        void push_point(int abscissa, int ordinate)
        {
            points.push_back(make_point(abscissa, ordinate));
            temp.push_back(make_point(0, 0));
            v.push_back(make_point(0, 0));
        }
        long long distance_between_closest_points()
        {
            sort(points.begin(), points.end());
            y_order_points = points;
            long long best = cmap(0, points.size());
            return best;
        }
    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));

            merge(y_order_points.begin() + left, y_order_points.begin() + mid, y_order_points.begin() + mid, y_order_points.begin() + right, temp.begin(), is_below);
            copy(temp.begin(), temp.begin() + (right - left), y_order_points.begin() + left);

            int v_size = 0;
            for(int i = left; i < right; ++i)
                if(abs(y_order_points[i].x - points[mid].x) <= best)
                    v[v_size++] = y_order_points[i];
            for(int i = 0; i < v.size() - 1; ++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 << sqrt(P.distance_between_closest_points());
    in.close();
    out.close();
    return 0;
}