Pagini recente » Istoria paginii runda/runda_ezoterica_4.5/clasament | Cod sursa (job #999471) | Istoria paginii runda/preoji_bv_11-12/clasament | Cod sursa (job #1706194) | Cod sursa (job #2642742)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int n;
vector <pair <int, int> > v;
long long Dist(pair <int, int> a, pair <int, int> b){
return 1LL * (a.first - b.first) * 1LL * (a.first - b.first) + 1LL * (a.second - b.second) * 1LL * (a.second - b.second);
}
void Merge(int st, int dr){
vector <pair <int, int> > aux;
int mid = (st + dr) / 2;
int p = mid + 1, j = st;
while (st <= mid && p <= dr){
if (v[st].second < v[p].second){
aux.push_back(v[st]);
++st;
}
else{
aux.push_back(v[p]);
++p;
}
}
while (st <= mid){
aux.push_back(v[st]);
++st;
}
while (p <= dr){
aux.push_back(v[p]);
++p;
}
for (int i = 0; i < aux.size(); ++i){
v[j++] = aux[i];
}
}
int GetMinDist(int st, int dr){
if (dr - st + 1 <= 3){
if (dr - st == 2){
Merge(st + 1, st + 2);
Merge(st, dr);
long long dist1 = Dist(v[st], v[st + 1]), dist2 = Dist(v[st], v[st + 2]), dist3 = Dist(v[st + 1], v[st + 2]);
return min(dist1, min(dist2, dist3));
}
else{
Merge(st, dr);
return Dist(v[st], v[st + 1]);
}
}
int mid = (st + dr) / 2;
int midX = v[mid].first;
long long left = GetMinDist(st, mid);
long long right = GetMinDist(mid + 1, dr);
long long minim = min(left, right);
Merge(st, dr);
vector <pair <int, int> > aux;
for (int i = st; i <= dr; ++i){
if (1LL * abs(midX - v[i].first) * abs(midX - v[i].first) <= minim){
aux.push_back(v[i]);
}
}
long long minimDist = (1LL << 60);
for (int i = 0; i < aux.size(); ++i){
for (int j = i + 1; j - i + 1 <= 8 && j < aux.size(); ++j){
minimDist = min(minimDist, Dist(aux[i], aux[j]));
}
}
return min(minim, minimDist);
}
int main(){
fin >> n;
for (int i = 0; i < n; ++i){
int x, y;
fin >> x >> y;
v.push_back({x, y});
}
sort(v.begin(), v.end());
fout << fixed << setprecision(6) << sqrt(GetMinDist(0, n - 1));
fin.close();
fout.close();
return 0;
}