Pagini recente » Cod sursa (job #2260312) | Cod sursa (job #2221604) | Cod sursa (job #1787167) | Cod sursa (job #2714120) | Cod sursa (job #1161710)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#define LINF ~(1LL<<63)
using namespace std;
pair<int, int> X[100010], Y[100010], aux[100010];
vector<pair<int, int> > pct;
int n;
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);
}
void citire()
{
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].first = X[i].second;
Y[i].second = X[i].first;
}
}
long long cmap(int st, int dr)
{
if(dr-st <= 1)
return LINF;
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)/2;
long long minim = 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) <= minim)
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++)
minim = min(minim, dist(pct[i], pct[j]));
return minim;
}
int main()
{
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
citire();
long long d = cmap(0, n);
double rez = sqrt(d);
printf("%lf\n", rez);
return 0;
}