Cod sursa(job #2446463)

Utilizator alexoloieriAlexandru Oloieri alexoloieri Data 8 august 2019 23:47:01
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.25 kb
#include <bits/stdc++.h>
using namespace std;

template <class T>
class closestPoints
{
#define pair std::pair
#define vector std::vector
#define lld long long
#define minn(a,b) ((a)<(b)?(a):(b))
#define infinity 2223372036854775807LL
#define uint unsigned int
private:
    vector<pair<T,T>>v;
    vector<pair<T,T>>xv,yv;
    lld distance(pair<T,T> &a, pair<T,T> &b)
    {
        return  1LL * (a.first - b.first) * (a.first - b.first) +
                1LL * (a.second - b.second) * (a.second - b.second);
    }
    lld minnn(T a, T b)
    {
        return minn(a,b);
    }
    lld divideEtImpera(int l, int r)
    {
        if (l >= r) return infinity;
        if (r - l == 1)
        {
            if (yv[l] > yv[l + 1])
                swap(yv[l],yv[l+1]);
            return distance(xv[l], xv[l+1]);
        }
        int m = (l + r) / 2;
        lld bst = minnn(divideEtImpera(l,m-1),divideEtImpera(m,r));
        sort(yv.begin()+l,yv.begin()+r+1);
        int sz = 0;
        for (int i=l; i<=r; ++i)
            if (abs(yv[i].second - xv[m].first) <= bst)
                v[sz++] = yv[i];
        for (int i=0; i<sz-1; ++i)
            for (int j=i+1; j<sz && j - i < 10; ++j)
                bst = minnn(bst, distance(v[i],v[j]));
        return bst;
    }
public:
    closestPoints() {}
    closestPoints(uint expectedMaximumN)
    {
        v.resize(expectedMaximumN);
        xv.resize(expectedMaximumN);
    }
    void addPoint(T a, T b)
    {
        xv.push_back(make_pair(a,b));
    }
    lld computeMinimumDistance()
    {
        sort(xv.begin(), xv.end());
        yv.clear();
        for (int i=0; i<xv.size(); ++i)
            yv.push_back(make_pair(xv[i].second, xv[i].first));
        v.resize(xv.size() + 1);
        return divideEtImpera(0,xv.size()-1);
    }
#undef vector
#undef pair
};

int main()
{
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);
    int n, x, y;
    scanf("%d",&n);
    closestPoints<long long> cmap;
    for (int i=1; i<=n; ++i)
    {
        scanf("%d %d",&x,&y);
        cmap.addPoint((long long)x,(long long)y);
    }
    long long closestD = cmap.computeMinimumDistance();
    cout<<setprecision(10)<<fixed<<sqrt(closestD)<<'\n';
    return 0;
}