Pagini recente » Cod sursa (job #3251375) | Cod sursa (job #902882) | Cod sursa (job #2880127) | Cod sursa (job #2767572) | Cod sursa (job #1014752)
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#define pii pair<int,int>
#define MP make_pair
#define x first
#define y second
#define i64 long long
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const int NMAX = int(1e5) + 2;
const i64 INF = 1ll<<60;
int N;
pii V[NMAX], X[NMAX], Y[NMAX];
inline i64 dist(const pii &a,const pii &b) {
return 1ll*(a.x - b.x) * (a.x - b.x) + 1ll*(a.y - b.y) * (a.y - b.y);
}
i64 solve(int st,int dr) {
if(dr - st == 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 , K = 0;
i64 bst = min(solve(st,mid),solve(mid,dr));
merge(Y + st, Y + mid, Y + mid, Y + dr, V);
for(int i = 0;i < dr - st;i++) {
Y[st + i] = V[i];
}
for(int i = st;i < dr;++i)
if(abs(Y[i].y - X[mid].x) <= bst) V[K++] = Y[i];
for(int i = 0;i < K;++i)
for(int j = i + 1;j < K && j - i <8;++j)
bst = min(bst,dist(V[i],V[j]));
return bst;
}
int main()
{
fin>>N;
for(int i = 0;i < N;++i)
fin>>X[i].x>>X[i].y;
sort(X,X + N);
for(int i = 0;i < N;++i)
Y[i] = MP(X[i].y,X[i].x);
double ret = sqrt(1.0*solve(0,N));
fout.precision(10);
fout<<ret;
return 0;
}