Pagini recente » Cod sursa (job #2559234) | Cod sursa (job #2653452) | Cod sursa (job #577312) | Cod sursa (job #266257) | Cod sursa (job #2345592)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("rmq.in");
ofstream fout("rmq.out");
const int oo = 1e9;
const int NMax = 100000;
int N, k;
pair<int, int> P[NMax + 5], X[NMax + 5];
void Read()
{
fin >> N;
for(int i = 0; i < N; i++)
fin >> P[i].first >> P[i].second;
sort(P + 1, P + N + 1);
}
int 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);
}
int DEI(int Left, int Right)
{
if(Right == Left)
return oo;
if(Right == Left + 1)
return Dist(P[Left], P[Right]);
int Mid = (Left + Right) / 2;
int A = DEI(Left, Mid);
int B = DEI(Mid + 1, Right);
int Min = min(A, B);
k = 0;
for(int i = Left; i <= Right; i++)
if(abs(P[i].first - P[Mid].first) <= Min)
X[++k] = P[i];
for(int i = 1; i <= k; i++)
for(int j = i + 1; j <= k; j++)
if(Dist(X[i], X[j]) < Min)
Min = Dist(X[i], X[j]);
return Min;
}
int main()
{
Read();
fout << fixed << setprecision(6) << sqrt(DEI(1, N));
}