Pagini recente » Cod sursa (job #1240526) | Cod sursa (job #1142741) | Cod sursa (job #1537713) | Cod sursa (job #1543075) | Cod sursa (job #1408433)
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int kMaxN = 100005;
const int64_t kInf = 4e18;
int N;
struct Point {
int x, y;
} p[kMaxN], aux[kMaxN];
int64_t ans = kInf;
bool LessX(const Point &p1, const Point &p2) {
return p1.x < p2.x;
}
bool LessY(const Point &p1, const Point &p2) {
return p1.y < p2.y;
}
int64_t Dist(const Point &p1, const Point &p2) {
int dx = p1.x - p2.x;
int dy = p1.y - p2.y;
return 1LL * dx * dx + 1LL * dy * dy;
}
void Read() {
freopen("cmap.in", "r", stdin);
scanf("%d", &N);
for (int i = 0; i < N; ++i)
scanf("%d%d", &p[i].x, &p[i].y);
}
void Solve(int l, int r) {
if (r - l == 1)
return;
if (r - l == 2) {
if (p[l].y > p[l + 1].y)
swap(p[l], p[l + 1]);
ans = min(ans, Dist(p[l], p[l + 1]));
return;
}
int m = (l + r) >> 1;
int xsep = p[m].x;
Solve(l, m);
Solve(m, r);
merge(p + l, p + m, p + m, p + r, aux, LessY);
memcpy(p + l, aux, (r - l) * sizeof(Point));
int nr = 0;
for (int i = l; i < r; ++i)
if (abs(p[i].x - xsep) < ans)
aux[nr++] = p[i];
for (int i = 0; i < nr - 1; ++i)
for (int j = i + 1; j < min(nr, i + 8); ++j)
ans = min(ans, Dist(aux[i], aux[j]));
}
void Print() {
freopen("cmap.out", "w", stdout);
printf("%.6f\n", sqrt(ans));
}
int main() {
Read();
sort(p, p + N, LessX);
Solve(0, N);
Print();
}