Pagini recente » Cod sursa (job #350953) | Cod sursa (job #460109) | Cod sursa (job #2966722) | Cod sursa (job #809462) | Cod sursa (job #1157319)
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<vector>
#define NMax 100005
using namespace std;
vector<pair<long long,long long> > V(NMax),X,Y;
const long long inf=4e18;
long long dist (pair<int,int> A, pair<int,int> B)
{
return (A.first-B.first)*(A.first-B.first)+(A.second-B.second)*(A.second-B.second);
}
long long modul (long long x)
{
if (x<0) return -x;
return x;
}
long long solve (int st, int dr)
{
int i,j;
if (st==dr)
return inf;
if (dr==st+1)
{
if (Y[st]>Y[dr])
swap(Y[st],Y[dr]);
return dist(X[st],X[dr]);
}
int mij=(st+dr)/2;
long long best=min(solve(st,mij),solve(mij+1,dr));
sort(Y.begin()+st,Y.begin()+dr+1);
int v_size=0;
for (i=st; i<=dr; i++)
if (modul(Y[i].second-X[mij].first)<=best)
V[v_size++]=Y[i];
for (i=0; i<v_size-1; i++)
for (j=i+1; j<v_size && j-i<8; j++)
best=min(best,dist(V[i],V[j]));
return best;
}
int main ()
{
int N,x,y,i;
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
scanf("%d",&N);
for (i=1; i<=N; i++)
{
scanf("%d%d",&x,&y);
X.push_back(make_pair(x,y));
}
sort(X.begin(),X.end());
for (i=0; i<X.size(); i++)
Y.push_back(make_pair(X[i].second,X[i].first));
printf("%.6lf\n",sqrt(solve(0,X.size()-1)));
return 0;
}