Pagini recente » Cod sursa (job #1601670) | Cod sursa (job #1256267) | Cod sursa (job #1785663) | Cod sursa (job #2062771) | Cod sursa (job #3306840)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <stack>
#include <cmath>
#include <iomanip>
// #include <bits/stdc++.h>
#define in fin
#define out fout
using namespace std;
using db = double;
using ll = long long;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
pair<int, int> v[100001];
bool cmpx(pair<int, int> &a, pair<int, int> &b){
if(a.first != b.first) return a.first < b.first;
else return a.second < b.second;
}
bool cmpy(pair<int, int> &a, pair<int, int> &b){
return a.second < b.second;
}
db dist(pair<int, int> a, pair<int, int> b){
return sqrt( db( (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second) ) );
}
db solve(int l, int r){
if(l == r) return 1e18;
if(l == r + 1) return dist(v[l], v[r]);
int m = (l + r) / 2;
db dmin = min( solve(l, m), solve(m + 1, r) );
vector< pair<int, int> > cand; // candidati care pot fi la merge
for(int i = l; i <= r; i++){
if( abs(v[i].first - v[m].first) <= dmin ) cand.push_back(v[i]);
}
sort(cand.begin(), cand.end(), cmpy);
for(int i = 0; i < cand.size(); i++){
for(int j = 1; j <= min(i, 8); j++){
dmin = min(dmin, dist(cand[i], cand[i - j]));
}
}
return dmin;
}
signed main(){
ios_base::sync_with_stdio(false);
in.tie(NULL);
int n; in >> n;
for(int i = 0; i < n; i++) in >> v[i].first >> v[i].second;
sort(v + 0, v + n, cmpx);
out << fixed << setprecision(6) << solve(0, n - 1) << '\n';
return 0;
}