Pagini recente » Cod sursa (job #727858) | Cod sursa (job #428910) | Cod sursa (job #985676) | Cod sursa (job #1851785) | Cod sursa (job #1503265)
#include <stdio.h>
#include <vector>
#include <algorithm>
#define Point pair<int, int>
#define x first
#define y second
#define mp make_pair
#define MAXN 100005
#define INF 0x7fffffffffffffff
#define MIN(a, b) (((a) < (b))?(a):(b))
using namespace std;
int n;
Point v[MAXN];
inline long long dist(Point A, Point B) {
long long dx = A.x - B.x;
long long dy = A.y - B.y;
return dx * dx + dy * dy;
}
bool Comp(Point a, Point b) {
return a.second < b.second;
}
long long solve(int l, int r) {
if(r - l + 1 <= 3) {
long long ans = INF;
for(int i = l; i < r; i++)
for(int j = i + 1; j <= r; j++) {
long long d = dist(v[l], v[r]);
ans = MIN(ans, d);
}
return ans;
}
int mid = (l + r) >> 1;
long long d1 = solve(l, mid);
long long d2 = solve(mid + 1, r);
long long ans = MIN(d1, d2);
int xx = v[mid].x;
vector<Point> a;
for(int i = l; i <= r; i++)
if(v[i].x > xx - sqrt(ans) - 1 && v[i].x < xx + sqrt(ans) + 1)
a.push_back(v[i]);
sort(a.begin(), a.end(), Comp);
for(int i = 0; i < a.size(); i++)
for(int j = i + 1; j < a.size() && j - i <= 7; j++) {
long long d = dist(a[i], a[j]);
ans = MIN(ans, d);
}
return ans;
}
int main()
{
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d %d", &v[i].x, &v[i].y);
sort(v + 1, v + n + 1);
printf("%.15f\n", sqrt(solve(1, n)));
return 0;
}