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
51
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 50;
int n;
struct node {
ll x_, y_;
} arr[maxn], t[maxn], tt[maxn];
ll calc(node &a, node &b) {
return (a.x_ - b.x_) * (a.x_ - b.x_) + (a.y_ - b.y_) * (a.y_ - b.y_);
}
void merge_sort(int l, int mid, int r) {
int i = l, j = l, k = mid + 1;
while (j <= mid && k <= r)
tt[i++] = (arr[j].y_ < arr[k].y_) ? arr[j++] : arr[k++];
while (j <= mid) tt[i++] = arr[j++];
while (k <= r) tt[i++] = arr[k++];
for (i = l; i <= r; ++i) arr[i] = tt[i];
}
ll divide(int l, int r) {
if (l == r) return LLONG_MAX;
int cnt = 0, mid = (l + r) / 2;
ll pivot = arr[mid].x_, mi = min(divide(l, mid), divide(mid + 1, r));
merge_sort(l, mid, r);
for (int i = l; i <= r; ++i) {
if ((arr[i].x_ - pivot) * (arr[i].x_ - pivot) < mi) t[++cnt] = arr[i];
}
for (int i = 1; i < cnt; ++i) {
for (int j = i + 1;
j <= cnt && (t[i].y_ - t[j].y_) * (t[i].y_ - t[j].y_) < mi; ++j) {
mi = min(mi, calc(t[i], t[j]));
}
}
return mi;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> arr[i].x_ >> arr[i].y_;
sort(arr + 1, arr + 1 + n, [](node &a, node &b) -> bool {
return a.x_ < b.x_ || (a.x_ == b.x_ && a.y_ < b.y_);
});
cout << divide(1, n);
}
|