Pagini recente » Cod sursa (job #1353892) | Cod sursa (job #3246128) | Cod sursa (job #2208814) | Cod sursa (job #3263653) | Cod sursa (job #2767844)
#include <bits/stdc++.h>
#define N_MAX 100003
using namespace std;
ifstream fin ("cmap.in");
ofstream fout ("cmap.out");
pair <long long, long long> x [N_MAX], y [N_MAX], z [N_MAX];
int n;
long long distance (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);
}
long long bs (int st, int dr) {
if (st >= dr)
return LONG_MAX;
if (dr - st + 1 == 2) {
if (y [st] > y [st + 1]) {
pair <long long, long long> var;
var = y [st];
y [st] = y [st + 1];
y [st + 1] = var;
}
return distance (x [st], x [st + 1]);
}
int mij = (st + dr) / 2, cnt = 0;
int i = st, j = mij + 1;
long long ans = min (bs (st, mij), bs (mij + 1, dr));
while (i <= mij && j <= dr){
if (y [i] <= y[j])
z [++ cnt] = y [i ++];
else z [++ cnt] = y [j ++];
}
for (; i <= mij; i ++)
z [++ cnt] = y [i];
for (; j <= dr; j ++)
z [++ cnt] = y [j];
for (i = st; i <= dr; i ++)
y [i] = z [i - st + 1];
cnt = 0;
for (i = st; i <= dr; i ++)
if (abs (y [i].second - x [mij].first) <= ans)
z [++ cnt] = y [i];
for (int i = 1; i <= cnt; i ++)
for (int j = i + 1; j <= cnt && j <= i + 7; j ++)
ans = min (ans, distance (z [i], z [j]));
return ans;
}
int main(){
fin >> n;
for (int i = 1; i <= n; i ++)
fin >> x [i].first >> x [i].second;
sort (x + 1, x + n + 1);
for (int i = 1; i <= n; i ++) {
y [i].second = x [i].first;
y [i].first = x [i].second;
}
fout << setprecision(6) << fixed << sqrt (bs (1, n));
return 0;
}