Pagini recente » Cod sursa (job #2495919) | Cod sursa (job #637977) | Cod sursa (job #2895391) | Cod sursa (job #1366600) | Cod sursa (job #2875001)
#include <bits/stdc++.h>
#define ll long long
#define inf 4e18
#define pii pair<int, int>
#define sc second
#define fr first
#define mp make_pair
#define Nmax 100005
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
pii x[Nmax], y[Nmax], v[Nmax];
int n;
ll dist(pii a, pii b)
{
return (ll)(a.fr-b.fr)*(a.fr-b.fr) + (ll)(a.sc-b.sc)*(a.sc-b.sc);
}
ll divide(int st, int dr)
{
if(dr-st<1)
return inf;
if(st+1==dr)
{
if(y[st].fr>y[st+1].fr)
swap(y[st], y[st+1]);
return dist(x[st], x[dr]);
}
int mij=(st+dr)/2;
ll d=min(divide(st, mij), divide(mij+1, dr));
merge(y+st, y+mij+1, y+mij+1, y+dr+1, v);
for(int i=0;i<dr-st+1;i++)
y[st+i]=v[i];
int k=0;
for(int i=st;i<=dr;i++)
if(abs(y[i].sc-x[mij].fr)<=d)
v[++k]=y[i];
for(int i=1;i<=k;i++)
for(int j=i+1; j<=k && j-i<8 ; j++)
d=min(d, dist(v[i], v[j]));
return d;
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
fin >> n;
for(int i=1;i<=n;i++)
fin >> x[i].fr >> x[i].sc;
sort(x+1, x+n+1);
for(int i=1;i<=n;i++)
{
y[i].fr=x[i].sc;
y[i].sc=x[i].fr;
}
ll rez=divide(1, n);
fout << fixed << setprecision(7) << sqrt(rez);
return 0;
}