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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
#include <climits>
#include <vector>
#include <queue>
#include <algorithm>
const int MAXN = 100005;
struct {
int x, y;
Point(int x = 0, int y = 0) : x(x), y(y) {}
} P[MAXN];
long long dist(const Point &a, const Point &b) {
return (long long) (a.x - b.x) * (a.x - b.x) + (long long) (a.y - b.y) * (a.y - b.y);
}
struct KDTree {
static bool cmp1(const Point &a, const Point &b) {
return a.y < b.y || (a.y == b.y && a.x < b.x);
}
static bool cmp2(const Point &a, const Point &b) {
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
std::priority_queue<long long, std::vector<long long>, std::greater<long long> > q;
struct Node {
Node *c[2];
Point p, r1, r2;
Node() {}
Node(Point p) : p(p), r1(p), r2(p) {
c[0] = c[1] = NULL;
}
void maintain() {
if (c[0]) {
r1.x = std::min(r1.x, c[0]->r1.x);
r1.y = std::min(r1.y, c[0]->r1.y);
r2.x = std::max(r2.x, c[0]->r2.x);
r2.y = std::max(r2.y, c[0]->r2.y);
}
if (c[1]) {
r1.x = std::min(r1.x, c[1]->r1.x);
r1.y = std::min(r1.y, c[1]->r1.y);
r2.x = std::max(r2.x, c[1]->r2.x);
r2.y = std::max(r2.y, c[1]->r2.y);
}
}
long long dist(const Point &p) {
return std::max(std::max(::dist(p, r1), ::dist(p, r2)),
std::max(::dist(p, Point(r1.x, r2.y)), ::dist(p, Point(r2.x, r1.y))));
}
void query(const Point &p, std::priority_queue<long long, std::vector<long long>, std::greater<long long> > &q) {
long long d = ::dist(p, this->p);
if (d > q.top()) q.pop(), q.push(d);
if (!(c[0] || c[1])) return;
long long dis[2] = {c[0] ? c[0]->dist(p) : INT_MIN,
c[1] ? c[1]->dist(p) : INT_MIN};
int k = dis[0] < dis[1];
c[k]->query(p, q);
if (c[k ^ 1] && dis[k ^ 1] > q.top()) c[k ^ 1]->query(p, q);
}
} *root, _pool[MAXN], *_cur;
KDTree() : root(NULL) {
_cur = _pool;
}
Node *build(Point *l, Point *r, int d = 0) {
if (l > r) return NULL;
if (l == r) return new (_cur++) Node(*l);
Point *mid = l + (r - l) / 2;
std::nth_element(l, mid, r + 1, d ? cmp1 : cmp2);
Node *u = new (_cur++) Node(*mid);
u->c[0] = build(l, mid - 1, d ^ 1);
u->c[1] = build(mid + 1, r, d ^ 1);
u->maintain();
return u;
}
long long query(Point P[], int n, int k) {
while (!q.empty()) q.pop();
for (int i = 0; i < k << 1; i++) q.push(-1);
for (int i = 1; i <= n; i++) root->query(P[i], q);
return q.top();
}
} kdT;
int main() {
int n, k;
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i++) scanf("%d %d", &P[i].x, &P[i].y);
kdT.root = kdT.build(P + 1, P + n);
printf("%lldn", kdT.query(P, n, k));
return 0;
}
|
近期评论