Cod sursa(job #1749631)

Utilizator meriniucrMeriniuc Razvan- Dumitru meriniucr Data 28 august 2016 15:04:58
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.95 kb
#include <bits/stdc++.h>

using ll = long long;

const ll INF = std::numeric_limits <ll>::max();

std::vector <std::pair <ll, ll> >  x;
std::vector <std::pair <ll, ll> >  y;
std::vector <std::pair <ll, ll> >  temp(100000);
int                                  n;

inline ll
dist(std::pair <ll, ll>& a,
     std::pair <ll, ll>& b)
{
    return ( (a.first - b.first) * (a.first - b.first) +
             (a.second - b.second) * (a.second - b.second) );
}

ll
haida(int beg,
      int end)
{
    int mid;
    ll  min;
    int i;
    int index;
    int j;

    if (beg == end)
    {
        return INF;
    }

    if (beg == end - 1)
    {
        if (y[beg].first > y[end].first)
        {
            std::swap(y[beg],
                      y[end]);

            return dist(x[beg],
                        x[end]);
        }
    }

    mid = (beg + end) / 2;
    min = std::min(haida(beg, mid),
                   haida(mid + 1, end));

    std::merge(y.begin() + beg, y.begin() + mid + 1, y.begin() + mid + 1, y.begin() + end + 1, temp.begin());
    std::copy(temp.begin(), temp.begin() + end - beg + 1, y.begin() + beg);

    index = 0;
    for (i = beg; i <= end; ++i)
    {
        if (abs(y[i].second - x[mid].first) <= min)
        {
            temp[index++] = y[i];
        }
    }

    for (i = 0; i < index; ++i)
    {
        for (j = i + 1; (j < index) and (j - i < 7); ++j)
        {
            if (dist(temp[i], temp[j]) < min)
            {
                min = dist(temp[i], temp[j]);
            }
        }
    }

    return min;
}

int main()
{
    std::ifstream mama("cmap.in");
    std::ofstream tata("cmap.out");
    
    mama >> n;

    x.resize(n);

    for (int i = 0; i < n; ++i)
    {
        mama >> x[i].first >> x[i].second;
    }

    std::sort(x.begin(),
              x.end());

    for (int i = 0; i < n; ++i)
    {
        y.push_back(std::make_pair(x[i].second, x[i].first));
    }

    tata << std::setprecision(15) << sqrt(haida(0, n - 1));
    return 0;
}