Pagini recente » Cod sursa (job #248669) | Cod sursa (job #1834561) | Cod sursa (job #1464285) | Cod sursa (job #2003348) | Cod sursa (job #3341870)
#include <fstream>
#include <climits>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const int oo = INT_MAX;
const int NMax = 100000; int N,K;
pair <int,int> Point[NMax + 5],NewPoint[NMax + 5];
void Read()
{
fin >> N;
for(int i = 1; i <= N; ++i)
{
int x,y;
fin >> x >> y;
Point[i] = make_pair(x,y);
}
sort(Point + 1, Point + N + 1);
}
long long 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) ;
}
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 + 1, 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]= make_pair(Point[i].second,Point[i].first);
}
sort(NewPoint + 1, NewPoint + K + 1);
for(int i = 1; i <= K; ++i)
for(int j = i + 1; j <= K && (j-i) < 8; ++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;
}