Pagini recente » Cod sursa (job #2987940) | Cod sursa (job #1590420) | Cod sursa (job #2999740) | Profil funkydvd | Cod sursa (job #2046869)
#include <bits/stdc++.h>
#define NMAX 100010
#define x first
#define y second
#define ll long long
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int N;
const ll INF = unsigned(-1);
pair <ll, ll> A[NMAX], V[NMAX];
inline ll euclid(pair <ll, ll> a, pair <ll, ll> b) {
return (b.y-a.y)*(b.y-a.y) + (b.x-a.x)*(b.x-a.x);
}
long long solve(int st, int dr) {
ll p, p1, p2;
if (dr-st == 0) {
return INF;
}
if (dr-st == 1) {
p = euclid(A[st], A[dr]);
return p;
} else if (dr-st == 2) {
p = min(euclid(A[st], A[st+1]), euclid(A[st+1], A[st+2]));
p = min(p, euclid(A[st], A[st+2]));
return p;
}
int mid = (st+dr)/2;
p1 = solve(st, mid);
p2 = solve(mid+1, dr);
p = min(p1, p2);
ll e = A[mid].x;
int k = 0;
for(int i = st; i <= dr; ++i) {
if(abs(A[i].y - e) <= p) {
V[++k] = A[i];
}
}
for(int i = 1; i <= k; ++i) {
for(int j = i + 1; j <= k and j < 8; ++j) {
p = min(p, euclid(V[i],V[j]));
}
}
return p;
}
int main()
{
fin>>N;
for(int i = 1; i <= N; ++i) {
fin>>A[i].x>>A[i].y;
}
sort(A+1, A+N+1);
fout<<fixed<<setprecision(6)<<sqrt(solve(1, N));
return 0;
}