Pagini recente » Cod sursa (job #692753) | Cod sursa (job #1283376) | Cod sursa (job #929540) | Cod sursa (job #2037108) | Cod sursa (job #2006364)
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
typedef long long i64;
int N;
vector<pair<i64, i64>>X;
vector<pair<i64,i64>>Y;
vector<pair<i64, i64>> aux;
i64 Distance(pair<i64, i64> p1, pair<i64, i64> p2)
{
return (p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y);
}
i64 solve(int left, int right, vector<pair<i64,i64>> &X, vector<pair<i64, i64>> &Y)
{
if (right - left <= 3)
{
i64 answ = 4e18;
for (int i = left; i < right; ++i)
for (int j = i + 1; j <= right; ++j)
{
if (Y[i] > Y[j])
swap(Y[i], Y[j]);
answ = min(answ, Distance(X[i], X[j]));
}
return answ;
}
int mid = (left + right) >> 1;
i64 best = min(solve(left, mid, X, Y), solve(mid + 1, right, X, Y));
merge(Y.begin() + left + 1, Y.begin() + mid + 1, Y.begin() + mid + 1, Y.begin() + right + 1, aux.begin());
copy(aux.begin(), aux.begin() + (right - left ), Y.begin() + left + 1);
int _size = 0;
for (int i = left; i <= right; ++i)
if (abs(X[mid].x - Y[i].y) <= best)
aux[_size++ ] = Y[i];
for (int i = 0; i < _size - 1; ++i)
for (int j = i + 1; j < _size && j - i < 8; ++j)
best = min(best, Distance(aux[i], aux[j]));
return best;
}
int main()
{
fin >> N;
X.resize(N + 1);
Y.resize(N + 1);
aux.resize(N + 1);
for (int i = 1; i <= N; ++i)
fin >> X[i].x >> X[i].y;
sort(X.begin(), X.end());
for (int i = 1;i <= N; ++i)
Y[i] = {X[i].y, X[i].x};
fout << fixed << setprecision(6) << sqrt(solve(1, N, X, Y)) << "\n";
return 0;
}