Pagini recente » Cod sursa (job #1761610) | Cod sursa (job #115130) | Cod sursa (job #1829912) | Cod sursa (job #1940084) | Cod sursa (job #2867175)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
#define NMAX 100005
const long long INF = 4e18;
int n;
vector<pair<long long, long long>> x, y, v(NMAX);
long long dist(pair<long long, long long> A, pair<long long, long long> B)
{
return (A.first - B.first) * (A.first - B.first)
+ (A.second - B.second) * (A.second - B.second);
}
long long solve(int st, int dr, vector<pair<long long, long long>> &X, vector<pair<long long,long long>> &Y)
{
if (st >= dr - 1) {
return INF;
}
else if (dr - st == 2){
if (Y[st] > Y[st+1])
swap(Y[st], Y[st+1]);
return dist(X[st], X[st+1]);
}
int mij = (st + dr) / 2;
long long best = min(solve(st, mij, X, Y), solve(mij, dr, X, Y));
merge(Y.begin() + st, Y.begin()+mij, Y.begin()+mij, Y.begin()+dr, v.begin());
copy(v.begin(), v.begin()+(dr-st), Y.begin()+st);
int vlen = 0;
for (int i=st;i<dr;i++){
if (abs(Y[i].second - X[mij].first) <= best)
v[vlen ++] = Y[i];
}
for (int i=0;i<vlen-1;i++){
for (int j=i+1;j<vlen && j-i<8;j++){
best = min(best, dist(v[i], v[j]));
}
}
return best;
}
int main() {
fin >> n;
x.resize(n);
y.resize(n);
for (int i=0;i<n;i++){
fin >> x[i].first >> x[i].second;
}
sort(x.begin(), x.end());
for (int i=0;i<n;i++){
y[i] = {x[i].second, x[i].first};
}
fout << fixed << setprecision(6) << sqrt(solve(0, n, x, y)) << '\n';
return 0;
}