学习套路.

题意同标题.

Solution

取前$k$大的无序对, 就是取前$2k$大的有序对. 我们枚举每个点, 用KD树加速找最大值的过程.

然后维护一个大小为$2k$的小根堆, 初始里面都是$0$, 每次找到一个距离, 如果比堆顶大, 就换掉堆顶. 这样是对的, 一开始一定比堆顶大, 后来如果堆里占满了$2k$个值, 加入求得的距离还要比堆顶小, 那至少也在$2k$以外了, 反之堆顶一定在$2k$以外了. KD树的作用实际只在于加速找当前点与各点较大距离的过程.

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int maxn = 1e+5 + 5;

int n, k, typ, ptr;
struct point {
  int x, y;
  point(int x_ = 0, int y_ = 0) : x(x_), y(y_) {}

  inline bool operator < (const point &rhs) const {
    if (typ) return (x == rhs.x) ? (y < rhs.y) : (x < rhs.x);
    else return (y == rhs.y) ? (x < rhs.x) : (y < rhs.y);
  }
}parr[maxn], ask;
struct KDn {
  int ch[2];
  point p, l, r;

  KDn(point P = point()) : p(P), l(P), r(P){
    ch[0] = ch[1] = 0;
  }
}t[maxn];
struct ll {
  long long a;
  ll() {a = 0;}

  inline ll operator=(long long rhs) {
    ll ret; ret.a = rhs;
    return ret;
  }
  inline bool operator<(const ll &rhs) const {
    return a > rhs.a;
  }
};
int tot;
priority_queue<ll> q;

inline LL getdis(const point &l, const point &r) {
  return 1ll * (l.x - r.x) * (l.x - r.x) + 1ll * (l.y - r.y) * (l.y - r.y);
}
inline LL sq(const LL &x) {
  return x * x;
}
inline LL approx(const int &lhs, const int &rhs) {
  return max(sq(t[lhs].p.x - t[rhs].l.x), sq(t[lhs].p.x - t[rhs].r.x)) + 
         max(sq(t[lhs].p.y - t[rhs].l.y), sq(t[lhs].p.y - t[rhs].r.y));
}
#define ls t[cur].ch[0]
#define rs t[cur].ch[1]
inline int rd() {
  register int x = 0, c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  return x;
}
inline void pushup(const int &cur, const int &son) {
  t[cur].l.x = min(t[cur].l.x, t[son].l.x);
  t[cur].l.y = min(t[cur].l.y, t[son].l.y);
  t[cur].r.x = max(t[cur].r.x, t[son].r.x);
  t[cur].r.y = max(t[cur].r.y, t[son].r.y);
}
int build(const int &l, const int &r, const int &dim) {
  int cur = ++ptr, mid = (l + r) >> 1;
  typ = dim;
  nth_element(parr + l, parr + mid, parr + r);
  t[cur] = KDn(*(parr + mid));
  if (l < mid) ls = build(l, mid - 1, dim ^ 1), pushup(cur, ls);
  if (r > mid) rs = build(mid + 1, r, dim ^ 1), pushup(cur, rs);
  return cur;
}
void query(int cur) {
  LL dx = getdis(ask, t[cur].p);
  if (dx > q.top().a) {
    ll p; p.a = dx;
    q.pop(); q.push(p);
  }
  LL disl = 0, disr = 0;
  if (ls) disl = approx(0, ls);
  if (rs) disr = approx(0, rs);
  ll tmp = q.top();
  if (disl > disr) {
    if (disl > tmp.a) query(ls); 
    tmp = q.top();
    if (disr > tmp.a) query(rs);
  } else {
    if (disr > tmp.a) query(rs); 
    tmp = q.top();
    if (disl > tmp.a) query(ls);
  }
}
#undef ls
#undef rs

int main() {
  n = rd(); k = rd();
  for (int i = 1; i <= n; ++i) {
    parr[i].x = rd(); parr[i].y = rd();
  }
  build(1, n, 1);
  ll tp; for (int i = 1; i <= 2 * k; ++i) q.push(tp);
  for (int i = 1; i <= n; ++i) {
    ask = parr[i]; t[0] = KDn(parr[i]);
    query(1);
  }
  printf("%lld\n", q.top().a);
  return 0;
}