Cod sursa(job #569333)

Utilizator SadmannCornigeanu Calin Sadmann Data 1 aprilie 2011 13:04:20
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 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> > V(NMAX),X,Y;
long long a,b;

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));
    merge(Y.begin()+st,Y.begin()+mid,Y.begin()+mid,Y.begin()+dr,V.begin());
    copy(V.begin(), V.begin() + (dr - st), Y.begin() + st);
    int v_size=0;
    for(i=st;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;
}