1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

10 5
0 0
0 1
1 0
1 1
2 0
2 1
1 2
0 2
3 0
3 1

1

9

  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
111
112
113
114

#include "ybwhead/ios.h"
const int maxn = 1e5 + 10;
struct node
{
    int x, y;
} a[maxn];
int opt;
bool cmp(node a, node b)
{
    if (opt)
        return a.y < b.y;
    else
        return a.x < b.x;
}
priority_queue<long long, vector<long long>, greater<long long>> q;
struct Kd_tree
{
    int root, cnt;
    struct nod
    {
        int ls, rs;
        node d;
        int mx[2], mi[2];
    } x[maxn << 2];
    void build(int &p, int l, int r)
    {
        if (l > r)
            return;
        if (!p)
            p = ++cnt;
        int mid = l + r >> 1;
        nth_element(a + l, a + mid, a + r + 1, cmp);
        x[p].d = a[mid];
        opt = !opt;
        build(x[p].ls, l, mid - 1);
        build(x[p].rs, mid + 1, r);
        x[p].mx[0] = x[p].mi[0] = x[p].d.x;
        x[p].mx[1] = x[p].mi[1] = x[p].d.y;
        if (x[p].ls)
        {
            x[p].mx[0] = max(x[p].mx[0], x[x[p].ls].mx[0]);
            x[p].mx[1] = max(x[p].mx[1], x[x[p].ls].mx[1]);
            x[p].mi[1] = min(x[p].mi[1], x[x[p].ls].mi[1]);
            x[p].mi[0] = min(x[p].mi[0], x[x[p].ls].mi[0]);
        }
        if (x[p].rs)
        {
            x[p].mx[0] = max(x[p].mx[0], x[x[p].rs].mx[0]);
            x[p].mx[1] = max(x[p].mx[1], x[x[p].rs].mx[1]);
            x[p].mi[1] = min(x[p].mi[1], x[x[p].rs].mi[1]);
            x[p].mi[0] = min(x[p].mi[0], x[x[p].rs].mi[0]);
        }
        opt = !opt;
    }
    void build(int l, int r)
    {
        build(root, l, r);
    }
    inline long long sqr(long long a)
    {
        return a * a;
    }
    inline long long dis(node a, node b)
    {
        return (sqr(a.x - b.x) + sqr(a.y - b.y));
    }
    inline long long dis1(node a, int b)
    {
        return (sqr(max(abs(a.x - x[b].mi[0]), abs(a.x - x[b].mx[0]))) + sqr(max(abs(a.y - x[b].mi[1]), abs(a.y - x[b].mx[1]))));
    }
#define inf LLONG_MAX / 10
    void query(int p, node y)
    {
        long long dl = -inf, dr = -inf;
        if (x[p].ls)
            dl = dis1(y, x[p].ls);
        if (x[p].rs)
            dr = dis1(y, x[p].rs);
        long long di = dis(y, x[p].d);
        if (q.top() < di)
        {
            q.pop();
            q.push(di);
        }
        if (dl > dr)
        {
            if (q.top() < dl)
                query(x[p].ls, y);
            if (q.top() < dr)
                query(x[p].rs, y);
        }
        else
        {
            if (q.top() < dr)
                query(x[p].rs, y);
            if (q.top() < dl)
                query(x[p].ls, y);
        }
    }
} T;
int n, k;
int main()
{
    yin >> n >> k;
    for (int i = 1; i <= n; i++)
        yin >> a[i].x >> a[i].y;
    T.build(1, n);
    for (int i = 1; i <= k << 1; i++)
        q.push(0);
    for (int i = 1; i <= n; i++)
        T.query(1, a[i]);
    yout << q.top() << endl;
    return 0;
}