k-d tree 裸题………………
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
int n, k, rot, nowD, din;
ll dui[205];
const ll oo=9e18;
struct Point{
int d[2], mn[2], mx[2], l, r;
int & operator[](int x){
return d[x];
}
bool operator<(const Point &x)const{
return d[nowD]<x.d[nowD];
}
}p[100005], T;
bool cmp(ll x, ll y){
return x>y;
}
struct KDTree{
Point t[100005];
void pushUp(int k){
int l=t[k].l, r=t[k].r;
for(int i=0; i<2; i++){
t[k].mn[i] = t[k].mx[i] = t[k][i];
if(l){
t[k].mn[i] = min(t[k].mn[i], t[l].mn[i]);
t[k].mx[i] = max(t[k].mx[i], t[l].mx[i]);
}
if(r){
t[k].mn[i] = min(t[k].mn[i], t[r].mn[i]);
t[k].mx[i] = max(t[k].mx[i], t[r].mx[i]);
}
}
}
int build(int l, int r, int now){
nowD = now;
int mid=(l+r)>>1;
nth_element(p+l, p+mid, p+r+1);
t[mid] = p[mid];
if(l<mid) t[mid].l = build(l, mid-1, now^1);
if(mid<r) t[mid].r = build(mid+1, r, now^1);
pushUp(mid);
return mid;
}
ll getDis(const Point &u, const Point &v){
return (ll)(u.d[1]-v.d[1])*(u.d[1]-v.d[1])+(ll)(u.d[0]-v.d[0])*(u.d[0]-v.d[0]);
}
ll simDis(int k){
ll re=0;
for(int i=0; i<2; i++){
ll tmp=max(abs(t[k].mn[i]-T[i]), abs(t[k].mx[i]-T[i]));
re += tmp * tmp;
}
return re;
}
void query(int k){
ll d=getDis(t[k], T), disl=-oo, disr=-oo;
int l=t[k].l, r=t[k].r;
if(d>dui[1]){
pop_heap(dui+1, dui+1+din, cmp);
dui[din] = d;
push_heap(dui+1, dui+1+din, cmp);
}
if(l) disl = simDis(l);
if(r) disr = simDis(r);
if(disl>disr){
if(disl>dui[1]) query(l);
if(disr>dui[1]) query(r);
}
else{
if(disr>dui[1]) query(r);
if(disl>dui[1]) query(l);
}
}
}kdt;
int main(){
cin>>n>>k;
k *= 2;
for(int i=1; i<=n; i++)
scanf("%d %d", &p[i][0], &p[i][1]);
rot = kdt.build(1, n, 0);
while(k--) dui[++din] = -oo;
for(int i=1; i<=n; i++){
T = p[i];
kdt.query(rot);
}
cout<<dui[1]<<endl;
return 0;
}