Pagini recente » Cod sursa (job #2547985) | Cod sursa (job #979325) | Cod sursa (job #864126) | Cod sursa (job #2406915) | Cod sursa (job #869956)
Cod sursa(job #869956)
#include <cmath>
#include <vector>
#include <cstdlib>
#include <fstream>
#include <iomanip>
#include <algorithm>
#define cin in
#define cout out
using namespace std;
typedef pair<int, int> pr;
typedef long long int lld;
const int NMAX = 100011;
pr X[NMAX], Y[NMAX], aux[NMAX];
inline lld _min(const lld& x, const lld& y) {return x <= y ? x : y;}
inline void _swap(pr& x, pr& y) {pr aux = x; x = y; y = aux;}
inline bool cmpY(const pr& x, const pr& y) {return x.second < y.second || (x.second == y.second && x.first < y.first);}
inline lld dSquare(const pr& x, const pr& y) {return 1LL * (x.first - y.first) * (x.first - y.first) + 1LL * (x.second - y.second) * (x.second - y.second);}
lld closestPoints(int left, int right)
{
lld minDSquare;
if(left >= right) return -1;
if(right - left <= 2)
{
minDSquare = dSquare(X[left], X[left + 1]);
for(int i = left; i < right; ++i)
{
for(int j = i + 1; j <= right; ++j)
{
minDSquare = _min(minDSquare, dSquare(X[i], X[j]));
}
}
}
else {
int i, j, k, middle;
middle = (left + right) >> 1;
minDSquare = _min(closestPoints(left, middle), closestPoints(middle + 1, right));
for(k = 0, i = left; i <= right; ++i)
{
if(1LL * abs(X[middle + 1].first - Y[i].first) <= minDSquare)
{
aux[k++] = Y[i];
}
}
k -= 1;
for(i = 0; i < k; ++i)
{
for(j = i + 1; j <= k && j - i < 8; ++j)
{
minDSquare = _min(minDSquare, dSquare(aux[i], aux[j]));
}
}
}
return minDSquare;
}
int main()
{
int N, i;
freopen("cmap.in", "rt", stdin);
freopen("cmap.out", "wt", stdout);
scanf("%d", &N);
for(i = 0; i < N; ++i)
{
scanf("%d%d", &X[i].first, &X[i].second);
Y[i] = X[i];
}
sort(X, X+N);
sort(Y, Y+N, cmpY);
printf("%.6lf\n", sqrt(1.0 * closestPoints(0, N-1)));
return EXIT_SUCCESS;
}