Cod sursa(job #1164351)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 1 aprilie 2014 23:54:43
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>

#define Nmax 100010

#define INF (1LL<<62)

using namespace std;
pair<int,int> X[Nmax],Y[Nmax],aux[Nmax];
vector<pair<int,int> > pct;
int N;

void read()
{
    scanf("%d",&N);
    for(int i = 0; i < N; ++i)
        scanf("%d%d",&X[i].first,&X[i].second);
    sort(X,X+N);
    for(int i = 0; i < N; ++i)
        Y[i] = X[i], swap(Y[i].first,Y[i].second);
}

inline long long dist(pair<int,int> a,pair<int,int> b)
{
    return 1LL*(a.first-b.first)*(a.first-b.first) +
           1LL*(a.second-b.second)*(a.second-b.second);
}

long long cmap(int st,int dr)
{
    if(dr - st <= 1) return INF;
    if(dr - st == 2)
    {
        if(Y[st] > Y[st+1])swap(Y[st],Y[st+1]);
        return dist(Y[st],Y[st+1]);
    }
    int mid = st + ((dr-st)>>1);
    long long best = min ( cmap(st,mid) , cmap(mid,dr) );
    ///merge(Y+st,Y+mid,Y+mid,Y+dr,aux); WTF ??
    ///copy(aux,aux+dr-st,Y+st);
    pct.clear();
    for(int i = st; i < dr; ++i)
        if(abs(X[mid].first - Y[i].second) <= best)
            pct.push_back(Y[i]);

    for(int i = 0; i < pct.size(); ++i)
        for(int j = i+1; j < pct.size() && j-i <= 8; ++j)
            best = min(best,dist(pct[i],pct[j]));
    return best;
}

int main()
{
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);

    read();
    long long d = cmap(0,N);
    double rez  = sqrt((double)d);
    printf("%lf\n",rez);
    return 0;
}