Pagini recente » Cod sursa (job #671985) | Cod sursa (job #1364102) | Cod sursa (job #2369765) | Cod sursa (job #933082) | Cod sursa (job #1164343)
#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);
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;
}