Pagini recente » Cod sursa (job #2839437) | Cod sursa (job #2467580) | Cod sursa (job #804119) | Cod sursa (job #1338981) | Cod sursa (job #1414495)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define Nmax 100005
using namespace std;
pair < int, int > Ox[Nmax],Oy[Nmax],Aux[Nmax];
long long sol=(1LL<<62);
inline long long Dist(pair <int,int> A, pair <int,int> B)
{
return 1LL*(A.first-B.first)*(A.first-B.first)+1LL*(A.second-B.second)*(A.second-B.second);
}
inline void Solve(int Left, int Right)
{
if(Left>=Right) return;
int mid=(Left+Right)/2;
Solve(Left,mid); Solve(mid+1,Right);
merge(Oy+Left,Oy+mid+1,Oy+mid+1,Oy+Right+1,Aux+1);
copy(Aux+1,Aux+Right-Left+2,Oy+Left);
for(int i=Left;i<=Right;++i)
for(int j=i+1;j<=i+7;++j) sol=min(sol,Dist(Oy[i],Oy[j]));
}
int main()
{
int i,n;
ifstream fin ("cmap.in");
ofstream fout ("cmap.out");
fin>>n;
for(i=1;i<=n;++i)
{
fin>>Ox[i].first>>Ox[i].second;
Oy[i].first=Ox[i].second; Oy[i].second=Ox[i].first;
}
sort(Ox+1,Ox+n+1);
Solve(1,n);
fout<<setprecision(10)<<fixed<<sqrt(1.0*sol);
return 0;
}