Pagini recente » Cod sursa (job #1844741) | Cod sursa (job #296548) | Cod sursa (job #2616997) | Cod sursa (job #1243348) | Cod sursa (job #1163808)
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#define INF ~(1LL << 63)
#define Nmax 100005
using namespace std;
pair <int, int> X[Nmax], Y[Nmax], Aux[Nmax];
vector <pair <int, int> > Punct;
int N;
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 Distanta(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 Distanta(Y[st], Y[st + 1]);
}
int mij = (st + dr) / 2;
long long Min = min(Cmap(st, mij), Cmap(mij, dr));
merge(Y + st, Y + mij, Y + mij, Y + dr, Aux);
copy(Aux, Aux + dr - st, Y + st);
Punct.clear();
for (int i = st; i < dr; ++i)
if (abs(X[mij].first - Y[i].second) <= Min)
Punct.push_back(Y[i]);
for (int i = 0; i < Punct.size(); ++i)
for (int j = i + 1; j < Punct.size() && j - i <= 8; ++j)
Min = min(Min, Distanta(Punct[i], Punct[j]));
return Min;
}
void Rezolvare()
{
long long Dist = Cmap(0, N);
double Dmin = sqrt(Dist);
printf("%lf\n", Dmin);
}
int main()
{
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
Citire();
Rezolvare();
return 0;
}