Pagini recente » Cod sursa (job #2279266) | Cod sursa (job #2811682) | Cod sursa (job #3176467) | Cod sursa (job #2323846) | Cod sursa (job #716408)
Cod sursa(job #716408)
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
struct point{long long x, y;};
long long d(point a, point b){
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
bool Compare(point a, point b){
if (a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
vector <point> v;
long long Dist(int l, int r){
if (r - l == 1) return d(v[l], v[r]);
long long i, j, q, dL, dR, m = (l + r) / 2;
dL = Dist(l, m);
dR = Dist(m, r);
q = min(dL, dR);
for (i = l; i <= r; i++)
if (abs(v[m].x - v[i].x) <= sqrt(q) && abs(v[m].y - v[i].y) <= sqrt(q))
for (j = i + 1; j < i + 8 && j <= r; j++)
q = min(d(v[i], v[j]), q) ;
return q;
}
int main(){
freopen("cmap.in", "r", stdin), freopen("cmap.out", "w", stdout);
int n, i;
scanf("%d", &n);
v.resize(n);
for (i = 0; i < n; i++)
scanf("%lld %lld", &v[i].x, &v[i].y);
sort(v.begin(), v.end(), Compare);
printf("%lf", sqrt(Dist(0, n - 1)));
}