Pagini recente » Cod sursa (job #1015719) | Cod sursa (job #1604881) | Cod sursa (job #1856838) | Cod sursa (job #3155921) | Cod sursa (job #605585)
Cod sursa(job #605585)
# include <algorithm>
# include <cstdio>
# include <cmath>
using namespace std;
# define x first
# define y second
typedef long long ll;
typedef pair <ll, ll> PR;
const char *FIN = "cmap.in", *FOU = "cmap.out";
const int MAX = 100005;
const ll oo = 4e18;
PR V[MAX], R[MAX], P[MAX];
int N;
ll dist (PR A, PR B) {
return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}
ll solve (int st, int dr) {
if (dr - st == 1) return oo;
if (dr - st == 2) {
if (R[st] > R[st + 1]) swap (R[st], R[st + 1]);
return dist (R[st], R[st + 1]);
}
int mij = st + dr >> 1;
ll sol = min (solve (st, mij), solve (mij, dr));
merge (R + st, R + mij, R + mij, R + dr, P);
copy (P, P + (dr - st), R + st);
int mare = -1;
for (int i = st; i < dr; ++i)
if (abs (R[i].y - P[mij].x) <= sol)
V[++mare] = R[i];
for (int i = 0; i < mare; ++i)
for (int j = i + 1; j < mare && j - i < 8; ++j)
sol = min (sol, dist (V[i], V[j]));
return sol;
}
int main (void) {
freopen (FIN, "r", stdin);
scanf ("%d", &N);
for (int i = 0; i < N; ++i)
scanf ("%lld %lld", &P[i].x, &P[i].y);
sort (P, P + N);
for (int i = 0; i < N; ++i)
R[i] = make_pair (P[i].y, P[i].x);
fprintf (fopen (FOU, "w"), "%.6lf", sqrt (solve (0, N)));
}