Pagini recente » Cod sursa (job #2661185) | Cod sursa (job #1272308) | Cod sursa (job #3260532) | Cod sursa (job #1029323) | Cod sursa (job #2333427)
#include <bits/stdc++.h>
#define f first
#define s second
#define inf (1<<63)-1
#define pi pair <ll , ll>
#define ll unsigned long long
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
ll n;
pair <ll, ll> v[100005];
ll dist( pi x, pi y)
{
return (x.f-y.f)*(x.f-y.f) +(x.s-y.s)*(x.s-y.s);
}
bool cmp( pair<ll,ll> a, pair<ll,ll> b ){
if( a.s < b.s ) return true;
if(a.s == b.s) return a.f < b.f;
return false;
}
ll cmap(ll left, ll right)
{
ll ans = inf;
if(left-right <= 3)
{
for(ll i = left; i < right; i++)
for(ll j = i+1; j <= right; j++)
ans = min(ans, dist(v[i], v[j]));
return ans;
}
ll mid = (left+right)/2;
ans = min(cmap(left, mid), cmap(mid+1, right));
vector <pi> add;
for(int i = left; i <= right; i++)
if(abs(v[i].f-v[mid].f) <= ans)
add.push_back(v[i]);
sort(add.begin(), add.end(), cmp);
for(ll i = 0; i < add.size(); i++)
for(ll j = i+1; j < add.size() && j-i<8; j++)
ans = min(ans, dist(add[i], add[j]));
return ans;
}
int main()
{
fin >> n;
for(ll i = 1; i <= n; i++)
fin >> v[i].f >> v[i].s;
sort(v+1, v+1+n);
fout << fixed << setprecision(7) << sqrt((double)cmap(1, n));
return 0;
}