Pagini recente » Cod sursa (job #1507411) | Cod sursa (job #593924) | Cod sursa (job #2337368) | Cod sursa (job #716502) | Cod sursa (job #1750817)
///Merge can wait...
#include <bits/stdc++.h>
using namespace std;
typedef long long i64; ///Deci de aici am eu obiceiul...
const i64 INF = 1LL << 62;
const int NMAX = 100005;
struct PII {
int x, y;
inline PII() { }
inline PII(int _x, int _y) {
x = _x;
y = _y;
}
};
PII pts[NMAX], aux[NMAX];
bool cmp_x(const PII &a, const PII &b) {
return (a.x==b.x) ? (a.y < b.y) : (a.x < b.x);
}
bool cmp_y(const PII &a, const PII &b) {
return (a.y==b.y) ? (a.x < b.x) : (a.y < b.y);
}
inline i64 dist(const PII &a, const PII &b) {
return i64(a.x - b.x) * (a.x - b.x) + i64(a.y - b.y) * (a.y - b.y);
}
i64 ant(int st, int dr) {
if(dr-st <= 2) {
i64 ans = INF;
for(int i=st; i<dr; ++i)
for(int j=i+1; j<=dr; ++j)
ans = min(ans, dist(pts[i], pts[j]));
return ans;
}
int med = (st + dr) / 2,
aln = 0;
i64 ans = min(ant(st, med), ant(med+1, dr));
for(int i=st; i<=dr; ++i) {
if(abs(i64(pts[med].x) - pts[i].x)*abs(pts[med].x - pts[i].x) <= ans) {
aux[aln++] = pts[i];
}}
sort(aux, aux + aln, cmp_y);
for(int i=0; i<aln; ++i)
for(int j=i+1; j<aln && j-i<8; ++j)
ans = min(ans, dist(pts[i], pts[j]));
return ans;
}
int main(void) {
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
int n, x, y;
scanf("%d", &n);
for(int i=0; i<n; ++i)
scanf("%d%d", &pts[i].x, &pts[i].y);
sort(pts, pts+n, cmp_x);
printf("%.6f\n",sqrt(1.*ant(0, n-1)));
fclose(stdin);
fclose(stdout);
return 0;
}