C++14(g++5.4) 解法, 执行用时: 163ms, 内存消耗: 11860K, 提交时间: 2019-06-28 11:47:45

#include <bits/stdc++.h>
#define MAXN 100005
#define fi first
#define se second
//#define ivorysi
using namespace std;
typedef long long int64;
int N,K;
priority_queue<int64,vector<int64>,greater<int64> > Q;
bool dimension;

struct point {
    int64 x,y;
}poi[MAXN];;
int64 dist(const point &a,const point &b) {
    return (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y);
}
bool cmp(point a,point b) {
    if(dimension) return a.y < b.y || (a.y == b.y && a.x < b.x);
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}
struct kdTree *null;
struct kdTree {
    point p,r1,r2;
    kdTree *lc,*rc;
    kdTree() {}
    kdTree(point P) {
	p = P;r1 = P;r2 = P;
	lc = rc = NULL;
    }
    void update() {
	r1.x = min(min(lc->r1.x,rc->r1.x),r1.x);
	r1.y = min(min(lc->r1.y,rc->r1.y),r1.y);
	r2.x = max(max(lc->r2.x,rc->r2.x),r2.x);
	r2.y = max(max(lc->r2.y,rc->r2.y),r2.y);
    }
    int64 dis(point P) {
	if(this == null) return -1e18;
	return max(max(dist(r1,P),dist(r2,P)),max(dist((point){r1.x,r2.y},P),dist((point){r2.x,r1.y},P)));
    }
}*rt;

kdTree* build(int l,int r,bool d) {
    if(l > r) return null;
    int mid = (l + r) >> 1;
    dimension = d;
    nth_element(poi + l,poi + mid,poi + r + 1,cmp);
    kdTree *res = new kdTree(poi[mid]);
    res->lc = build(l,mid - 1,d ^ 1);
    res->rc = build(mid + 1,r,d ^ 1);
    res->update();
    return res;
}
void query(kdTree *u,point q) {
    if(u == null) return;
    int64 d = dist(u->p,q);
    if(d >= Q.top()) Q.pop(),Q.push(d);
    kdTree *s = u->lc->dis(q) > u->rc->dis(q) ? u->lc : u->rc;
    kdTree *z = s == u->lc ? u->rc : u->lc;
    query(s,q);
    if(z->dis(q) >= Q.top()) query(z,q);
}
void Init() {
    null = new kdTree;
    null->r1 = (point){0x7fffffff,0x7fffffff};
    null->r2 = (point){-1,-1};
    scanf("%d%d",&N,&K);
    for(int i = 1 ; i <= 2 * K ; ++i) Q.push(-1);
    for(int i = 1 ; i <= N ; ++i) {
	scanf("%lld%lld",&poi[i].x,&poi[i].y);
    }
    rt = build(1,N,0);
}
void Solve() {
    Init();
    for(int i = 1 ; i <= N ; ++i) query(rt,poi[i]);
    printf("%lld\n",Q.top());
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
}

C++11(clang++ 3.9) 解法, 执行用时: 84ms, 内存消耗: 5852K, 提交时间: 2019-03-09 17:52:22

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define sqr(x) (x)*(x)
#define ll long long
#define N 100005
#define inf 1000000000000000ll
using namespace std;
int n,k,Q,root,lc[N],rc[N];
ll mn[N][2],mx[N][2];
priority_queue<ll,vector<ll>,greater<ll> > q;
struct data
{
	ll d[2];
	friend bool operator <(data a,data b)
	{
		return a.d[Q]!=b.d[Q]?a.d[Q]<b.d[Q]:a.d[Q^1]<b.d[Q^1];
	}
}tmp,val[N];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline ll calc(data a,data b){return sqr(a.d[0]-b.d[0])+sqr(a.d[1]-b.d[1]);}
void pushup(int x)
{
	F(i,0,1)
	{
		mn[x][i]=mx[x][i]=val[x].d[i];
		mn[x][i]=min(mn[x][i],min(mn[lc[x]][i],mn[rc[x]][i]));
		mx[x][i]=max(mx[x][i],max(mx[lc[x]][i],mx[rc[x]][i]));
	}
}
int build(int l,int r,int k)
{
	if (l>r) return 0;
	int mid=(l+r)>>1;
	Q=k;
	nth_element(val+l,val+mid,val+r+1);
	lc[mid]=build(l,mid-1,k^1);
	rc[mid]=build(mid+1,r,k^1);
	pushup(mid);
	return mid;
}
ll get(int x)
{
	if (!x) return 0;
	ll ret=0;
	F(i,0,1) ret+=max(sqr(mx[x][i]-tmp.d[i]),sqr(mn[x][i]-tmp.d[i]));
	return ret;
}
void query(int x)
{
	if (!x) return;
	ll dl=get(lc[x]),dr=get(rc[x]),d=calc(tmp,val[x]);
	if (d>q.top()) q.pop(),q.push(d);
	if (dl>dr)
	{
		if (dl>q.top()) query(lc[x]);
		if (dr>q.top()) query(rc[x]);
	}
	else
	{
		if (dr>q.top()) query(rc[x]);
		if (dl>q.top()) query(lc[x]);
	}
}
int main()
{
	n=read();k=read();
	F(i,1,n) val[i].d[0]=read(),val[i].d[1]=read();
	F(i,0,1) mn[0][i]=inf,mx[0][i]=-inf;
	root=build(1,n,0);
	F(i,1,2*k) q.push(0);
	F(i,1,n) tmp=val[i],query(root);
	printf("%lld\n",q.top());
	return 0;
}