Pagini recente » Cod sursa (job #1539064) | Cod sursa (job #1116616) | Cod sursa (job #2787024) | Cod sursa (job #1179967) | Cod sursa (job #1415189)
#include <bits/stdc++.h>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
#define nmax 100001
pair<int,int> a[nmax],b[nmax],c[nmax];
int n,i;
long long dist(pair<int,int> a,pair<int,int> b)
{
return 1ll*(1ll*(a.first-b.first)*(a.first-b.first)+1ll*(a.second-b.second)*(a.second-b.second));
}
long long min_d(int st,int dr)
{
int i,j;
if(st==dr) return 1ll<<60;
if(st+1==dr)
{
return dist(a[st],a[dr]);
}
int mid=(st+dr)>>1;
int line=a[mid].second,l;
long long minn=min(min_d(st,mid),min_d(mid+1,dr));
merge(a+st,a+mid+1,a+mid+1,a+dr+1,b);
l=0;
for(i=0;i<dr-st+1;++i)
if(1ll*(line-b[i].second)*(line-b[i].second)<=minn) c[++l]=b[i];
for(i=1;i<=l;++i)
{
for(j=1;j<=7;++j)
if(i+j<=l)
minn=min(minn,dist(c[i],c[i+j]));
}
for(i=st;i<=dr;++i) a[i]=b[i-st ];
return minn;
}
int main()
{
f>>n;
for(i=1;i<=n;++i) f>>a[i].first>>a[i].second;
sort(a+1,a+n+1);
for(i=1;i<=n;++i) swap(a[i].first,a[i].second);
g<<fixed<<setprecision(6)<<sqrt(min_d(1,n));
return 0;
}