Cod sursa(job #1214335)

Utilizator cosmo0093Raduta Cosmin cosmo0093 Data 30 iulie 2014 03:01:48
Problema Cele mai apropiate puncte din plan Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 3.1 kb
#include <fstream>
#include <vector>
#include <ctime>
#include <cstdlib>
#include <utility>
#include <cmath>
#include <iomanip>
#include <climits>

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

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

void quickSortX(std::vector<Point> &myV, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int l = left;
    int r = right;
    Point pivot = myV[left + rand() % (right - left)];
    while (l < r)
    {
        while (myV[l].x < pivot.x)
        {
            l++;
        }
        while (pivot.x < myV[r].x)
        {
            r--;
        }
        if (l <= r)
        {
            std::swap(myV[l], myV[r]);
            l++;
            r--;
        }
    }
    quickSortX(myV, left, r);
    quickSortX(myV, l, right);
}

void quickSortY(std::vector<Point> &myV, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int l = left;
    int r = right;
    Point pivot = myV[left + rand() % (right - left)];
    while (l < r)
    {
        while (myV[l].y < pivot.y)
        {
            l++;
        }
        while (pivot.y < myV[r].y)
        {
            r--;
        }
        if (l <= r)
        {
            std::swap(myV[l], myV[r]);
            l++;
            r--;
        }
    }
    quickSortY(myV, left, r);
    quickSortY(myV, l, right);
}

double_t bruteForce(std::vector<Point> &myX, int l, int r)
{
    double_t d = LONG_MAX;
    for (int i = l; i < r; i++)
    {
        for (int j = i + 1; j <= r; j++)
        {
            d = std::min(d, dist(myX[i], myX[j]));
        }
    }
    return d;
}

double_t getPair(std::vector<Point> &myX, std::vector<Point> &myY, int l, int r)
{
    if ((r - l + 1) <= 3) {
        return bruteForce(myX, l, r);
    }
    int m = (r + l) / 2;
    Point center = myX[m];
    double_t c = std::min(getPair(myX, myY, l, m), getPair(myX, myY, m + 1, r));
    std::vector<Point> myClose;
    for (int i = l; i <= r; i++)
    {
        if (abs(myY[i].x - center.x) < c)
        {
            myClose.push_back(myY[i]);
        }
    }
    int nSize = (int)myClose.size();
    for (int i = 0; i < nSize - 1; i++)
    {
        int index = std::min(nSize, i + 8);
        for (int j = i + 1; j < index; j++)
        {
            c = std::min(c, dist(myClose[i], myClose[j]));
        }
    }
    return c;
}

int main()
{
    srand(time(NULL));
    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_t a, b;
        in >> a >> b;
        myX.push_back(Point(a, b));
        myY.push_back(Point(a, b));
    }
    in.close();
    quickSortX(myX, 0, nV - 1);
    quickSortY(myY, 0, nV - 1);
    double_t d = getPair(myX, myY, 0, nV);
    out << std::fixed << std::setprecision(6) << d << '\n';
    out.close();
    return 0;
}