Cod sursa(job #569289)

Utilizator SadmannCornigeanu Calin Sadmann Data 1 aprilie 2011 12:03:20
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include<fstream>
#include<vector>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#define NMAX 100001
#define INF 4e18
#define LL long long

using namespace std;
ifstream in("cmap.in");
FILE *out=fopen("cmap.out","wt");
int i,n;

vector< pair<LL,LL> > X,Y,V(NMAX);
long long a,b;
int v_size;

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

int main()
{
    in>>n;
    for(i=1;i<=n;i++)
    {
        in>>a>>b;
        X.push_back(make_pair(a,b));
    }
    sort(X.begin(),X.end());
    for(i=0;i<n;i++)
        Y.push_back(make_pair(X[i].second,X[i].first));
    fprintf(out,"%.06lf",sqrt(go(0,X.size())) );

    return 0;
}

LL go(int st,int dr)
{
    if(st>=dr-1)
        return INF;
    else
        if(dr-st==2)
        {
            if(Y[st]>Y[st+1])
                swap(Y[st],Y[st+1]);
            return dist(X[st],X[st+1]);
        }
    int mid=(st+dr)/2;
    LL best=min(go(st,mid),go(mid,dr));
    for(i=st,v_size=0;i<dr;i++)
        if(abs(Y[i].second-X[mid].first)<=best)
            V[v_size++]=Y[i];
    for(i=0;i<v_size-1;i++)
        for(int j=i+1;j<v_size && j-i<8;j++)
            best=min(best,dist(V[i],V[j]));
    return best;
}