Pagini recente » Borderou de evaluare (job #3171567) | Cod sursa (job #1227017) | Cod sursa (job #659180) | Cod sursa (job #425476) | Cod sursa (job #2345594)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("rmq.in");
ofstream fout("rmq.out");
const long long oo = 1e9;
const long long NMax = 100000;
long long N, k;
pair<long long, long long> P[NMax + 5], X[NMax + 5];
void Read()
{
fin >> N;
for(long long i = 0; i < N; i++)
fin >> P[i].first >> P[i].second;
sort(P + 1, P + N + 1);
}
long long Dist(pair<long long, long long> A, pair<long long, long long> B)
{
return (A.first - B.first) * (A.first - B.first) + (A.second - B.second) * (A.second - B.second);
}
long long DEI(long long Left, long long Right)
{
if(Right == Left)
return oo;
if(Right == Left + 1)
return Dist(P[Left], P[Right]);
long long Mid = (Left + Right) / 2;
long long A = DEI(Left, Mid);
long long B = DEI(Mid + 1, Right);
long long Min = min(A, B);
k = 0;
for(long long i = Left; i <= Right; i++)
if(abs(P[i].first - P[Mid].first) <= Min)
X[++k] = P[i];
for(long long i = 1; i <= k; i++)
for(long long 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));
}