Pagini recente » Borderou de evaluare (job #2657824) | Cod sursa (job #3341676) | Cod sursa (job #2889301) | Cod sursa (job #988020) | Cod sursa (job #3340419)
#include <bits/stdc++.h>
#define fi first
#define se second
#define punct pair<int, int>
#define ld long double
#define INF 1e9
#define MAXN 100005
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const int BULAN=10;
punct v[MAXN];
int n;
ld dist(punct a, punct b) {
return (a.fi-b.fi)*(a.fi-b.fi)+(a.se-b.se)*(a.se-b.se);
}
ld solve(int a, int b) {
ld ans=INF;
if (b-a<3) {
for (int i=a; i<=b; i++) {
for (int j=i+1; j<=b; j++) {
ans=min(ans, dist(v[a], v[b]));
}
}
return ans;
}
ans=min(solve(a, (a+b)/2), solve((a+b)/2+1, b));
int verticala=v[(a+b)/2+1].fi;
vector<punct>x;
for (int i=a; i<=b; i++) {
if (abs(v[i].fi-verticala)<=ans) x.push_back({v[i].se, v[i].fi});
}
sort(x.begin(), x.end());
int m=x.size();
for (int i=1; i<m; i++) {
for (int j=i+1; j<=min(m-1, i+BULAN); j++) {
ans=min(ans, dist(x[i], x[j]));
}
}
return ans;
}
int main()
{
fin>>n;
for (int i=0; i<n; i++) {
fin>>v[i].fi>>v[i].se;
}
sort(v, v+n);
fout<<fixed<<setprecision(8)<<sqrt(solve(0, n-1));
return 0;
}