Cod sursa(job #1214552)

Utilizator cosmo0093Raduta Cosmin cosmo0093 Data 30 iulie 2014 19:07:32
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.66 kb
#include <fstream>
#include <ctime>
#include <cstdlib>
#include <utility>
#include <cmath>
#include <iomanip>
#include <iostream>

#define MAX 100001

double myV[MAX][2];
int myY[MAX];
int aux[MAX];

double dist(int a, int b)
{
    return sqrt((myV[b][0] - myV[a][0]) * (myV[b][0] - myV[a][0]) + (myV[b][1] - myV[a][1]) * (myV[b][1] - myV[a][1]));
}

void quickSort(int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int l = left, r = right;
    double pivot = myV[l + rand() % (r - l)][0];
    while (l < r)
    {
        while (myV[l][0] < pivot)
        {
            l++;
        }
        while (myV[r][0] > pivot)
        {
            r--;
        }
        if (l <= r)
        {
            std::swap(myV[l], myV[r]);
            l++;
            r--;
        }
    }
    quickSort(l, right);
    quickSort(left, r);
}

double closest(int l, int r)
{
    if (l + 1 == r)
    {
        if (myV[l][1] > myV[r][1])
        {
            myY[l] = r;
            myY[r] = l;
        }
        return dist(l, r);
    }
    if (l == r)
    {
        return LONG_MAX;
    }
    int m = (l + r) / 2;
    double c = std::min(closest(l, m), closest(m + 1, r));
    double cenX = myV[m][0];

    int lefty = l, righty = m + 1, k = 0;
    while (lefty <= m && righty <= r)
    {
        if (myV[myY[lefty]][1] < myV[myY[righty]][1])
        {
            aux[k++] = myY[lefty];
            lefty++;
        }
        else
        {
            aux[k++] = myY[righty];
            righty++;
        }
    }
    while (lefty <= m)
    {
        aux[k++] = myY[lefty];
        lefty++;
    }
    while (righty <= r)
    {
        aux[k++] = myY[righty];
        righty++;
    }
    int index = l;
    for (int i = 0; i < k; i++)
    {
        myY[index] = aux[i];
        index++;
    }
    k = 0;
    for (int i = l; i <= r; i++)
    {
        if (abs(myV[myY[i]][0] - cenX) <= c)
        {
            aux[k++] = myY[i];
        }
    }
    for (int i = 0; i < k - 1; i++)
    {
        for (int j = i + 1; j < std::min(k, i + 8); j++)
        {
            c = std::min(c, dist(aux[i], aux[j]));
        }
    }
    return c;
}

int main()
{
    srand(time(NULL));
    std::ifstream in("cmap.in");
    std::ofstream out("cmap.out");
    int nV;
    in >> nV;
    for (int i = 0; i < nV; i++)
    {
        double a, b;
        in >> a >> b;
        myV[i][0] = a;
        myV[i][1] = b;
        myY[i] = i;
    }
    in.close();
    quickSort(0, nV - 1);
    out << std::fixed << std::setprecision(6) << closest(0, nV - 1) << '\n';
    out.close();
    return 0;
}