Pagini recente » Cod sursa (job #2391926) | Cod sursa (job #22534) | Cod sursa (job #794499) | Cod sursa (job #2563858) | Cod sursa (job #1267212)
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define DIM 100010
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
vector< pair<long long, long long> > P;
pair<long long, long long> R[DIM], Q[DIM];
int n, i, x, y;
inline long long modul(long long x) {
return (x > 0 ? x : -x);
}
long long dist(pair<long long, long long> a, pair<long long, long long> b) {
return (a.first - b.first)*(a.first - b.first) +
(a.second - b.second)*(a.second - b.second);
}
void interclasare(int st, int m, int dr) {
int i = st, j = m+1, k = st-1;
while (i<=m && j<=dr)
if (P[i].second < P[j].second) {
R[++k] = P[i++];
} else {
R[++k] = P[j++];
}
for (;i<=m;i++)
R[++k] = P[i];
for (;j<=dr;j++)
R[++k] = P[j];
for (i=st;i<=dr;i++)
P[i] = R[i];
}
long long rec(int st, int dr) {
long long r;
if (dr-st == 1) {
r = dist(P[st], P[dr]);
interclasare(st, st, dr);
return r;
}
if (dr - st == 2) {
r = min(dist(P[st], P[st+1]), min(dist(P[st], P[st+2]), dist(P[st+1], P[st+2])));
interclasare(st, st, st+1);
interclasare(st, st+1, dr);
return r;
}
int m = (st + dr)/2;
long long rst = rec(st, m);
long long rdr = rec(m+1, dr);
interclasare(st, m, dr);
long long minim = min(rst, rdr);
int t = 0;
for (int i=st; i<=dr;i++) {
if (modul( P[m].first - P[i].first ) <= minim) {
Q[++t] = P[i];
}
}
for (int i=1; i<t;i++) {
for (int j = i+1; j<=t && j<=i+7; j++)
minim = min(minim, dist(Q[i], Q[j]));
}
return minim;
}
int min(long long a, long long b) {
return a < b ? a : b;
}
int main() {
fin>>n;
for (i=1;i<=n;i++) {
fin>>x>>y;
P.push_back(make_pair(x, y));
}
sort(P.begin(), P.end());
fout<<setprecision(7)<<fixed<<(double)sqrt(rec(1, n))<<"\n";
return 0;
}