Pagini recente » Cod sursa (job #320364) | Cod sursa (job #1985193) | Cod sursa (job #3169462) | Cod sursa (job #2388662) | Cod sursa (job #869908)
Cod sursa(job #869908)
#include <cmath>
#include <fstream>
#include <iomanip>
#include <algorithm>
#define cin in
#define cout out
using namespace std;
typedef long long int llu;
typedef pair<int, int> pr;
const int NMAX = 100011;
ifstream in("cmap.in");
ofstream out("cmap.out");
pr vx[NMAX], vy[NMAX], aux[NMAX];
inline llu min(const llu& x, const llu& y) {return x <= y ? x : y;}
inline void swap(pr& x, pr& y) {pr aux = x; x = y; y = aux;}
inline bool compY(const pr& x, const pr& y) {return x.second < y.second || (x.second == y.second && x.first < y.first);}
inline llu 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);}
llu closestPoints(int left, int right)
{
llu minDSquare;
if(left >= right) return -1;
if(right - left <= 10)
{
minDSquare = dSquare(vx[left], vx[left + 1]);
for(int i = left; i < right; ++i)
{
for(int j = i + 1; j <= right; ++j)
{
minDSquare = min(minDSquare, dSquare(vx[i], vx[j]));
if(vy[i].second > vy[j].second)
{
swap(vy[i], vy[j]);
}
}
}
}
else {
int i, j, k, middle;
middle = (left + right) >> 1;
minDSquare = min(closestPoints(left, middle), closestPoints(middle + 1, right));
merge(vy + left, vy + middle + 1, vy + middle + 1, vy + right + 1, aux, compY);
copy(aux, aux + right + 1, vy + left);
for(i = left, k = 0; i <= right; ++i)
{
if(abs(vx[middle].first - vy[i].first) <= minDSquare)
{
aux[k++] = vy[i];
}
}
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;
}
inline double closestPoints(int N)
{
copy(vx, vx, vy);
sort(vx, vx + N);
return sqrt(1.0 * closestPoints(0, N-1));
}
int main()
{
int N, i;
cin >> N;
for(i = 0; i < N; ++i)
{
cin >> vx[i].first >> vx[i].second;
}
cout << fixed << setprecision(6) << closestPoints(N) << '\n';
return EXIT_SUCCESS;
}