题面

Sol

维护一个小根堆，初始里面放\(2*k\)个元素(因为点对可能算两遍)

每个点\(KDTree\)暴力查询是否有与这个点距离大于堆顶的，替换堆顶就好了

# include 
    
     # define IL inline# define RG register# define Fill(a, b) memset(a, b, sizeof(a))using namespace std;typedef long long ll;IL int Input(){    RG int x = 0, z = 1; RG char c = getchar();    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);    return x * z;}const int maxn(1e5 + 5);int n, k, op, rt, num, cnt;priority_queue 
     
       q;struct Point{    int d[2];    IL int operator <(RG Point a) const{        return d[op] < a.d[op];    }} a[maxn];struct KDTree{    int ch[2], d[2], mn[2], mx[2];} tr[maxn];IL void Chkmax(RG int &x, RG int y){    if(y > x) x = y;}IL void Chkmin(RG int &x, RG int y){    if(y < x) x = y;}IL void Update(RG int x){    RG int ls = tr[x].ch[0], rs = tr[x].ch[1];    tr[x].mx[0] = tr[x].mn[0] = tr[x].d[0];    tr[x].mx[1] = tr[x].mn[1] = tr[x].d[1];    if(ls){        Chkmin(tr[x].mn[0], tr[ls].mn[0]), Chkmin(tr[x].mn[1], tr[ls].mn[1]);        Chkmax(tr[x].mx[0], tr[ls].mx[0]), Chkmax(tr[x].mx[1], tr[ls].mx[1]);    }    if(rs){        Chkmin(tr[x].mn[0], tr[rs].mn[0]), Chkmin(tr[x].mn[1], tr[rs].mn[1]);        Chkmax(tr[x].mx[0], tr[rs].mx[0]), Chkmax(tr[x].mx[1], tr[rs].mx[1]);    }}IL int Build(RG int l, RG int r, RG int nop){    op = nop;    RG int x = (l + r) >> 1, nw = ++cnt;    nth_element(a + l, a + x, a + r + 1);    tr[nw].d[0] = a[x].d[0], tr[nw].d[1] = a[x].d[1];    if(l < x) tr[nw].ch[0] = Build(l, x - 1, nop ^ 1);    if(x < r) tr[nw].ch[1] = Build(x + 1, r, nop ^ 1);    Update(nw);    return nw;}# define Sqr(x) ((x) * (x))IL ll Dis(RG ll x1, RG ll y1, RG ll x2, RG ll y2){    return Sqr(x1 - x2) + Sqr(y1 - y2);}IL ll Calc(RG int p, RG ll x, RG ll y){    RG ll ret = 0;    ret = max(ret, Dis(tr[p].mn[0], tr[p].mn[1], x, y));    ret = max(ret, Dis(tr[p].mx[0], tr[p].mn[1], x, y));    ret = max(ret, Dis(tr[p].mn[0], tr[p].mx[1], x, y));    ret = max(ret, Dis(tr[p].mx[0], tr[p].mx[1], x, y));    return ret;}IL void Query(RG int x, RG Point p){    RG ll dis = Dis(tr[x].d[0], tr[x].d[1], p.d[0], p.d[1]);    if(dis > -q.top()) q.pop(), q.push(-dis);    if(tr[x].ch[0]){        if(Calc(tr[x].ch[0], p.d[0], p.d[1]) > -q.top()) Query(tr[x].ch[0], p);    }    if(tr[x].ch[1]){        if(Calc(tr[x].ch[1], p.d[0], p.d[1]) > -q.top()) Query(tr[x].ch[1], p);    }}int main(){    n = Input(), k = Input();    for(RG int i = 1; i <= n; ++i) a[i].d[0] = Input(), a[i].d[1] = Input();    rt = Build(1, n, 0);    for(RG int i = k + k; i; --i) q.push(0);    for(RG int i = 1; i <= n; ++i) Query(rt, a[i]);    printf("%lld\n", -q.top());    return 0;}