Pagini recente » Cod sursa (job #1205449) | Cod sursa (job #3145527) | Cod sursa (job #1976667) | Cod sursa (job #861662) | Cod sursa (job #1489818)
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const int NMAX = 100505;
const long long INF = (1LL << 62);
struct pt {
int x, y;
bool operator < (const pt& other) const {
if (x < other.x) return true;
if (x > other.x) return false;
return y < other.y;
}
};
int n, cnt;
pt A[NMAX], sortedY[NMAX], auxY[NMAX], special[NMAX];
void read() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &A[i].x, &A[i].y);
}
}
inline long long dist(pt& a, pt& b) {
return 1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y);
}
long long closest(int l, int r) {
if (l == r) {
return INF;
}
if (r - l == 1) {
return dist(A[l], A[r]);
}
int mid = (l + r) >> 1;
long long best = min(closest(l, mid), closest(mid + 1, r));
// merge
merge(sortedY + l, sortedY + mid + 1, sortedY + mid + 1, sortedY + r + 1, auxY + l);
copy(auxY + l, auxY + r + 1, sortedY + l);
cnt = 0;
for (int i = l; i <= r; i++)
if (1LL * (sortedY[i].x - A[mid].x) * (sortedY[i].x - A[mid].x) <= best) {
special[++cnt] = sortedY[i];
}
for (int i = 1; i <= cnt; i++)
for (int j = i + 1; j <= i + 7 && j <= cnt; j++) {
best = min(best, dist(special[i], special[j]));
}
return best;
}
int main() {
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
read();
sort(A + 1, A + n + 1);
copy(A + 1, A + n + 1, sortedY + 1);
long long res = closest(1, n);
printf("%.10lf\n", sqrt((double)res));
return 0;
}