Pagini recente » Cod sursa (job #1447996) | Cod sursa (job #1425908) | Cod sursa (job #2423587) | Cod sursa (job #841060) | Cod sursa (job #3341882)
#include <fstream>//383250
#include <climits>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const long long oo = 4e18;
const int NMax = 100000; int N,K;
pair <long long,long long> Point[NMax + 5], NewPoint[NMax + 5];
void Read()
{
fin >> N;
for(int i = 1; i <= N; ++i)
{
long long x,y;
fin >> x >> y;
Point[i] = make_pair(x,y);
}
sort(Point + 1, Point + N + 1);
}
long long dist(pair <long long,long long> a, pair <long long,long long> b)
{
return 1LL*(a.first - b.first) * (a.first - b.first) + 1LL*(a.second - b.second) * (a.second - b.second) ;
}
long long DEI(int Left, int Right)
{
if (Left == Right)
return oo;
if (Left == Right-1)
return dist(Point[Left],Point[Right]);
int Mid = (Left + Right) / 2;
long long A = DEI(Left,Mid);
long long B = DEI(Mid, Right);
long long Min = min(A,B);
for(int i = Left,K = 0; i <= Right; ++i)
{
if( abs(Point[i].first-Point[Mid].first)< Min)
NewPoint[++K]= Point[i];
}
sort(NewPoint+1, NewPoint+K+1);
for(int i = 1; i <= K; ++i)
for(int j = i + 1; j <= K; ++j)
Min = min(Min, dist(NewPoint[i],NewPoint[j]));
return Min;
}
int main()
{
Read();
fout << fixed << setprecision(6) << sqrt(DEI(1,N)) << "\n";
return 0;
}