Pagini recente » Cod sursa (job #655216) | Cod sursa (job #289388) | Cod sursa (job #2283055) | Cod sursa (job #913291) | Cod sursa (job #1308240)
#include <iostream>
#include <math.h>
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <utility>
#define nmax 100005
#define ll long long
using namespace std;
pair<ll,ll> point[nmax];
pair<ll,ll> V[nmax];
int N;
ll dist(pair<ll, ll> p1, pair<ll, ll> p2) {
return (p1.first - p2.first)*(p1.first - p2.first) + (p1.second - p2.second) * (p1.second - p2.second);
}
ll minimalDistance(int left, int right) {
int mid = (left + right) >> 1;
if (left >= right)
return 1LL << 62;
if (left + 1 == right) {
if ( point[left].second > point[right].second )
swap(point[left], point[right]);
return dist(point[left], point[right]);
}
ll minDist = min(minimalDistance(left, mid), minimalDistance(mid + 1, right));
merge(point + left, point + mid + 1, point + mid + 1, point + right + 1, V);
int nr = 0;
for (int i = left; i <= right; i++) {
if ( abs(point[i].first - point[mid].first) <= minDist)
V[++nr] = point[i];
}
for (int i=left; i<right; i++) {
for (int j=i+1; j<=min(i+5, nr); j++)
minDist = min(minDist, dist(V[j], V[i]));
}
return minDist;
}
int main() {
freopen("cmap.in", "r", stdin);
scanf("%d", &N);
for (int i=1; i<=N; ++i) {
scanf("%lld %lld", &point[i].first, &point[i].second);
}
sort(point + 1, point + N + 1);
freopen("cmap.out","w",stdout);
printf("%lf", sqrt((double)minimalDistance(1, N)));
return 0;
}