Pagini recente » Cod sursa (job #1667082) | Cod sursa (job #903848) | Cod sursa (job #772441) | Cod sursa (job #2156325) | Cod sursa (job #1428641)
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const int NMax = 100005;
const long long oo = (1LL<<60);
int N;
pair<int,int> P[NMax];
void Read()
{
fin>>N;
for(int i=1; i<=N; ++i)
{
int x,y;
fin>>x>>y;
P[i]= make_pair(x,y);
}
sort(P+1,P+N+1);
}
long long Distance(pair<int,int> A, pair<int,int> B)
{
return 1LL*(B.first-A.first)*(B.first-A.first)+(B.second-A.second)*(B.second-A.second);
}
long long DEI(int Left, int Right)
{
if(Left == Right)
return oo;
if(Right-Left == 1)
return Distance(P[Left],P[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);
vector< pair <int, int> > V;
for(int i = Left; i<=Right; i++)
if(abs(P[i].first-P[Mid].first)<=Min)
V.push_back(P[i]);
for(int i=0;i< (int) V.size(); ++i)
for(int j=i+1;j< (int) V.size(); ++j)
Min = min(Min,Distance(V[i],V[j]));
return Min;
}
int main()
{
Read();
fout<<fixed<<setprecision(6)<<sqrt(DEI(1,N));
return 0;
}