Pagini recente » Cod sursa (job #2216513) | Cod sursa (job #2197616) | Cod sursa (job #1949577) | Cod sursa (job #1792566) | Cod sursa (job #3196511)
#include <bits/stdc++.h>
#pragma GCC optimize ("03")
using namespace std;
#define INFILE "cmap.in"
#define OUTFILE "cmap.out"
typedef long long ll;
const ll INF = 1e18;
const int N_MAX = 1e5 + 5;
struct Point {
ll x, y;
Point() : x(0LL), y(0LL) {}
Point(ll _x, ll _y) : x(_x), y(_y) {}
};
int n;
ll ans = INF;
Point v[N_MAX];
bool compareX(Point a, Point b){
return (a.x < b.x);
}
bool compareY(Point a, Point b){
return (a.y < b.y);
}
ll getDistance(Point a, Point b){
ll deltaX = (a.x - b.x);
ll deltaY = (a.y - b.y);
return (deltaX * deltaX + deltaY * deltaY);
}
void getMinDistance(int left, int right){
if(left == right) return;
ll middle = ((left + right) >> 1);
ll x = v[middle].x;
vector<Point> pt;
getMinDistance(left, middle);
getMinDistance(middle + 1, right);
for(int i = left; i <= right; ++i){
if((v[i].x - x) * (v[i].x - x) <= ans) pt.push_back(v[i]);
}
sort(pt.begin(), pt.end(), compareY);
for(int i = 0; i < pt.size(); ++i){
for(int j = i + 1; j < pt.size(); ++j){
if((pt[j].y - pt[i].y) * (pt[j].y - pt[i].y) > ans) break;
ans = min(ans, getDistance(pt[i], pt[j]));
}
}
}
void solve(){
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> v[i].x >> v[i].y;
}
sort(v + 1, v + n + 1, compareX);
getMinDistance(1, n);
long double result = sqrt((long double)ans);
cout << fixed << setprecision(6) << result << '\n';
}
int main(){
ios_base::sync_with_stdio(false);
freopen(INFILE, "r", stdin);
freopen(OUTFILE, "w", stdout);
cin.tie(0), cout.tie(0);
solve();
return 0;
}