Pagini recente » Cod sursa (job #342611) | Cod sursa (job #571727) | Cod sursa (job #3252006) | Cod sursa (job #908469) | Cod sursa (job #2439981)
#include <bits/stdc++.h>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
typedef long long ll;
const int inf = 4e16;
vector <pair <ll, ll > > v,x;
int n;
bool cmp(const pair <ll, ll> &X, const pair <ll, ll> &Y){
return X.second < Y.second;
}
inline ll pow(ll X){
return X * X;
}
inline ll modul(ll X){
return max(X, -X);
}
inline ll distance(const pair <ll, ll> &X, const pair <ll, ll> &Y){
return pow(X.first - Y.first) + pow(X.second - Y.second);
}
ll solve(int lo, int hi){
int i,j;
if(hi - lo <= 3){
ll dist = inf;
for(i = lo ; i < hi ; i++)
for(j = i + 1 ; j < hi ; j++)
dist = min(dist, distance(v[i], v[j]));
return dist;
}
int mid = (lo + hi) / 2;
ll dist = min(solve(lo,mid), solve(mid, hi));
int k = 0;
for(i = lo ; i < hi ; i++)
if(modul(v[mid].first - v[i].first) < dist)
x[k++] = v[i];
sort(x.begin(), x.begin() + k, cmp);
for(i = 0 ; i < k ; i++)
for(j = i + 1 ; j < k && j - i < 8; j++)
dist = min(dist, distance(x[i], x[j]));
return dist;
}
int main(){
int i;
f >> n;
x.resize(n);
v.resize(n);
for(i = 0 ; i < n ; i++)
f >> v[i].first >> v[i].second;
sort(v.begin(), v.end());
g << fixed << setprecision(7) << sqrt(solve(0,n));
return 0;
}