Cod sursa(job #1214324)

Utilizator cosmo0093Raduta Cosmin cosmo0093 Data 30 iulie 2014 02:21:07
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 3.59 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;
};

double 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 bruteForce(std::vector<Point> myX)
{
    double d = LONG_MAX;
    for (int i = 0; i < (int)myX.size() - 1; i++)
    {
        for (int j = i + 1; j < (int)myX.size(); j++)
        {
            d = std::min(d, dist(myX[i], myX[j]));
        }
    }
    return d;
}

double getPair(std::vector<Point> myX, std::vector<Point> myY)
{
    if (myX.size() <= 3)
    {
        return bruteForce(myX);
    }
    int nSize = (int)myX.size();
    int m = nSize / 2;
    std::vector<Point> leftX, rightX;
    for (int i = 0; i < m; i++)
    {
        leftX.push_back(myX[i]);
    }
    for (int i = m; i < nSize; i++)
    {
        rightX.push_back(myX[i]);
    }
    Point center = leftX.back();
    std::vector<Point> leftY, rightY;
    nSize = (int)myY.size();
    for (int i = 0; i < nSize; i++)
    {
        if (center.x > myY[i].x)
        {
            leftY.push_back(myY[i]);
        }
        else
        {
            rightY.push_back(myY[i]);
        }
    }
    double c = std::min(getPair(leftX, leftY), getPair(rightX, rightY));
    std::vector<Point> myClose;
    for (int i = 0; i < nSize; i++)
    {
        if (abs(myY[i].x - center.x) < c)
        {
            myClose.push_back(myY[i]);
        }
    }
    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 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 d = getPair(myX, myY);
    out << std::fixed << std::setprecision(6) << d << '\n';
    out.close();
    return 0;
}