KDT 板子，但被卡了。

const int N = 4e5 + 5, K = 2;
const ll inf = 1e16;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, k;
	int d;
	struct Point {
		ll x[K];
		bool operator < (const Point& b) const {
			return x[d] < b.x[d];
		}
	}a[N];
	priority_queue<ll> q;
#define sq(x) ((x) * (x))
	ll get_dis (Point a, Point b) { return sq(a.x[0] - b.x[0]) + sq(a.x[1] - b.x[1]); }
	struct KDT {
		struct node {
			int l, r;
			ll mx[K], mn[K];
			Point p;
		} t[N];
		int tot;
		ll limd (Point x, int y) {
			return max(sq(x.x[0] - t[y].mx[0]), sq(x.x[0] - t[y].mn[0])) + max(sq(x.x[1] - t[y].mx[1]), sq(x.x[1] - t[y].mn[1]));
		}
		void pushup (int p) {
			for(int i = 0; i < K; i++) t[p].mx[i] = t[p].mn[i] = t[p].p.x[i];
			if (t[p].l) {
				for(int i = 0; i < K; i++) t[p].mx[i] = max(t[p].mx[i], t[t[p].l].mx[i]);
				for(int i = 0; i < K; i++) t[p].mn[i] = min(t[p].mn[i], t[t[p].l].mn[i]);
			} 
		   	if (t[p].r) {
				for(int i = 0; i < K; i++) t[p].mx[i] = max(t[p].mx[i], t[t[p].r].mx[i]);
				for(int i = 0; i < K; i++) t[p].mn[i] = min(t[p].mn[i], t[t[p].r].mn[i]);
			}
		}
		void build (int &p, int l, int r, int curd) {
			if (l > r) return;
			p = ++tot;
			int mid = (l + r) >> 1;
			d = curd;
			nth_element(a + l, a + mid, a + r + 1);
			t[p].p = a[mid];
			build (t[p].l, l, mid - 1, curd ^ 1);
			build (t[p].r, mid + 1, r, curd ^ 1);
			pushup(p);
		}
		void query (int p, Point val) {
			if (!p) return;
			ll dl = -inf, dr = -inf;
			if (t[p].l) dl = limd(val, t[p].l);
			if (t[p].r) dr = limd(val, t[p].r);
			ll dis = get_dis(t[p].p, val);
			if(dis > -q.top())q.pop(), q.push(-dis);
			if(dl > dr) {
				if(dl > -q.top()) query(t[p].l, val);
				if(dr > -q.top()) query(t[p].r, val);
			} else {
				if(dr > -q.top()) query(t[p].r, val);
				if(dl > -q.top()) query(t[p].l, val);
			}
		}
	}t;
	int main () {
		n = Read(), k = Read();
		for (int i = 1; i <= n; i++) a[i].x[0] = Read(), a[i].x[1] = Read();
		int rt;
		t.build(rt, 1, n, 0);
		for(int i = 1; i <= 2 * k; i++)q.push(0);
		for(int i = 1; i <= n; i++) t.query(1, a[i]);
		printf("%lld\n", -q.top());
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}

还可以旋转卡壳。

与 KDT 类似，也是维护一个大 $k$ 的小根堆，每次取最远的放入。

具体地，每次旋转卡壳取相隔最远的两个点，把所有点和这两个点的距离丢进小根堆里，然后把这两个点删掉，这个过程重复 $k$ 次。

const int N = 4e5 + 5, K = 2;
const ll inf = 1e16;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	struct node {
		ll x, y, id;
	} p[N], s[N];
	ll n, k, siz, tmp, top, ans;
	bool vis[N];
	priority_queue<ll, vector<ll>, greater<ll> >q;
	inline bool cmp(node a, node b) { return a.x != b.x ? a.x < b.x : a.y < b.y; }
	inline ll dist(node a, node b) { return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); }
	inline ll cross(node a, node b, node c) { return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); }
	inline void insert(ll x) {
		if(siz < k)siz++, q.push(x);
		else if(siz >= k && q.top() < x)q.pop(), q.push(x);
	}
	inline void del(ll x) {
		vis[x] = 1;
		for(ll i = 1; i <= n; i++)if(!vis[i])insert(dist(p[i], p[x]));
	}
	inline void init() {
		top = 0;
		for(ll i = 1; i <= n; i++) {
			if(vis[i])continue;
			for(; top >= 2 && cross(s[top - 1], s[top], p[i]) >= 0; top--);
			s[++top] = p[i];
		}
		for(ll i = s[top].id - 1, pre = top; i >= s[1].id; i--) {
			if(vis[i])continue;
			for(; top - pre >= 1 && cross(s[top - 1], s[top], p[i]) >= 0; top--);
			s[++top] = p[i];
		}
		s[0] = s[--top];
	}
	inline node Find() {
		init();
		ll ans = 0, a1, a2;
		if(top == 2) {
			return (node) {
				s[1].id, s[2].id
			};
		}
		for(ll i = 0, j = 2; i < top; i++) {
			while(cross(s[i], s[i + 1], s[j]) > cross(s[i], s[i + 1], s[j + 1]))j = (j + 1) % top;
			if(dist(s[i], s[j]) > ans)ans = dist(s[i], s[j]), a1 = s[i].id, a2 = s[j].id;
			if(dist(s[i + 1], s[j]) > ans)ans = dist(s[i + 1], s[j]), a1 = s[i + 1].id, a2 = s[j].id;
		}
		return (node) { a1, a2 };
	}
	int main() {
		n = tmp = Read(), k = Read();
		for(int i = 1; i <= n; i++)p[i].x = Read(), p[i].y = Read();
		sort(p + 1, p + n + 1, cmp);
		for(int i = 1; i <= n; i++)p[i].id = i;
		for(; k && tmp >= 2; k--, tmp -= 2) {
			node a = Find();
			del(a.x); del(a.y);
		}
		printf ("%lld", q.top());
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}