Pagini recente » Cod sursa (job #2904330) | Cod sursa (job #2482442) | Cod sursa (job #3270764) | Cod sursa (job #2481636) | Cod sursa (job #2046856)
#include <bits/stdc++.h>
#define NMAX 100010
#define x first
#define y second
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int N;
pair <int, int> A[NMAX], V[NMAX];
inline int euclid(pair <int, int> a, pair <int, int> b) {
return (b.y-a.y)*(b.y-a.y) + (b.x-a.x)*(b.x-a.x);
}
int solve(int st, int dr) {
int p, p1, p2;
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(p2, 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);
int 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) {
int euc = euclid(V[i],V[j]);
p = min(p, euc);
}
}
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;
}