Cod sursa(job #1214128)

Utilizator cosmo0093Raduta Cosmin cosmo0093 Data 29 iulie 2014 18:18:36
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.88 kb
#include <fstream>
#include <vector>
#include <ctime>
#include <cstdlib>
#include <utility>
#include <cmath>
#include <iomanip>
#include <climits>

struct Point
{
    Point(double a, double b)
    {
        x = a;
        y = b;
    }
    double x, y;
};

bool compX(Point a, Point b)
{
    if (a.x < b.x)
    {
        return true;
    }
    else
    {
        return a.y < b.y;
    }
}

bool compY(Point a, Point b)
{
    if (a.y < b.y)
    {
        return true;
    }
    else
    {
        return a.x < b.x;
    }
}

double dist(Point a, Point b)
{
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

void quickSort(std::vector<Point> myV, int left, int right, bool (*comps)(Point a, Point b))
{
    if (left >= right)
    {
        return;
    }
    int l = left;
    int r = right;
    Point pivot = myV[left + rand() % (right - left)];
    while (l < r)
    {
        while ((*comps)(myV[l], pivot))
        {
            l++;
        }
        while ((*comps)(pivot, myV[r]))
        {
            r--;
        }
        if (l <= r)
        {
            std::swap(myV[l], myV[r]);
            l++;
            r--;
        }
    }
    quickSort(myV, left, r, comps);
    quickSort(myV, l, right, comps);
}

double getPair(std::vector<Point> myX, std::vector<Point> myY, int l, int r)
{
    if ((r - l) <= 3)
    {
        double a = INT_MAX;
        double b = INT_MAX;
        for (int i = l; i < r; i++)
        {
            for (int j = i + 1; j <= r; j++)
            {
                b = dist(myX[i], myX[j]);
                if (b < a)
                {
                    a = b;
                }
            }
        }
        return a;
    }
    int m = (r + l) / 2;
    double d = std::min(getPair(myX, myY, l, m), getPair(myX, myY, m, r));
    std::vector<Point> myAux;
    for (int i = l; i <= r; i++)
    {
        if (abs(myY[i].x - myX[m].x) <= d)
        {
            myAux.push_back(myY[i]);
        }
    }
    double dd = INT_MAX;
    for (unsigned i = 0; i < myAux.size() - 1; i++)
    {
        for (unsigned j = i + 1; j < myAux.size() && j - i < 8; j++)
        {
            dd = dist(myAux[i], myAux[j]);
            if (dd < d)
            {
                d = dd;
            }
        }
    }
    return d;
}

int main()
{
    std::ifstream in("cmap.in");
    std::ofstream out("cmap.out");
    int nV;
    in >> nV;
    std::vector<Point> myX, myY;
    for (int i = 0; i < nV; i++)
    {
        double a, b;
        in >> a >> b;
        myX.push_back(Point(a, b));
        myY.push_back(Point(a, b));
    }
    in.close();
    quickSort(myX, 0, nV - 1, &compX);
    quickSort(myY, 0, nV - 1, &compY);
    double d = getPair(myX, myY, 0, nV - 1);
    out << std::fixed << std::setprecision(6) << sqrt(d);
    out.close();
    return 0;
}