1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#define ll long long
using namespace std;
const int maxn = 100010;
double ans = 1E30;
struct point {
double x, y;
} points[maxn], tmp_points[maxn];
int cmp_x(const point &a, const point &b) { return a.x != b.x ? a.x < b.x : a.y < b.y;}
int cmp_y(const point &a, const point &b) { return a.y < b.y; }
ll sqr(double x) { return x * x; }
double dist(point a, point b) { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)); }
void divide(int l, int r) {
if (r - l <= 3) {
for (int i = l; i <= r; i++)
for (int j = i + 1; j <= r; j++)
ans = min(dist(points[i], points[j]),ans);
sort(points + l, points + r + 1, &cmp_y);
return;
}
int m = (l + r) >> 1;
int mid_x = points[m].x;
divide(l, m);
divide(m + 1, r);
inplace_merge(points + l, points + m + 1, points + r + 1, &cmp_y);
int tmp_cnt = 0;
for (int i = l; i <= r; i++)
if (abs(points[i].x - mid_x) < ans) {
for (int j = tmp_cnt - 1; j >= 0 && points[i].y - tmp_points[j].y < ans; j--)
ans = min(dist(points[i], points[j]),ans);
tmp_points[tmp_cnt++] = points[i];
}
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> points[i].x >> points[i].y;
sort(points, points + n, &cmp_x);
divide(0, n - 1);
cout << fixed << setprecision(4) << ans;
return 0;
}
|
