Pagini recente » Cod sursa (job #1256731) | Cod sursa (job #2254154) | Cod sursa (job #915725) | Cod sursa (job #2185932) | Cod sursa (job #1025645)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <utility>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
const int MaxArraySize = 100001;
const long long Inf = 1LL << 61
long long n, ans;
pair<long long, long long> vec[MaxArraySize], x[MaxArraySize], y[MaxArraySize];
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 modul(long long val) {
if (val < 0)
return -val;
return val;
}
long long dive_et_imp(int st, int dr, pair<long long, long long> x[], pair<long long, long long> y[]) {
if (st >= dr - 1)
return Inf;
if (dr - st == 2) {
if (y[st] > y[st + 1])
swap(y[st], y[st + 1]);
return dist(x[st], x[st + 1]);
}
long long sol, mij, i, j, m = 0;
mij = st + (dr - st) / 2;
sol = min(dive_et_imp(st, mij, x, y), dive_et_imp(mij, dr, x, y));
sort(y + st, y + dr);
for (i = st; i < dr; ++i)
if (sol >= modul(y[i].second - x[mij].first))
vec[m++] = y[i];
for (i = 0; i < m - 1; ++i) {
for (j = i + 1; j < m && j - i < 8; ++j)
sol = min(sol, dist(vec[i], vec[j]));
}
return sol;
}
int main() {
int i;
f >> n;
for (i = 0; i < n; ++i)
f >> x[i].first >> x[i].second;
sort(x, x + n);
for (i = 0; i < n; ++i)
y[i] = make_pair(x[i].second, x[i].first);
ans = dive_et_imp(0, n, x, y);
g << fixed << setprecision(6) << sqrt(ans) << "\n";
f.close();
g.close();
return 0;
}