记录编号	540346	评测结果	AAAAAAAAAA
题目名称	[CQOI2016]K远点对	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	0.494 s
提交时间	2019-08-21 14:15:28	内存使用	16.42 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+7;
int m,n,ans,k;
struct node
{
	int x,y;
} s[N];
int D[N],L[N],R[N],U[N];
int d[N],lc[N],rc[N];
int sqr(int x) {return x*x;}
double sq(double x) {return x*x;}
bool cmp1(node a,node b) {return a.x<b.x;}
bool cmp2(node a,node b) {return a.y<b.y;}
priority_queue<int,vector<int>,greater<int> > que;
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;
}
void maintain(int x)
{
	L[x]=R[x]=s[x].x,U[x]=D[x]=s[x].y;
	if (lc[x]) L[x]=min(L[x],L[lc[x]]),R[x]=max(R[x],R[lc[x]]),U[x]=min(U[x],U[lc[x]]),D[x]=max(D[x],D[lc[x]]);
	if (rc[x]) L[x]=min(L[x],L[rc[x]]),R[x]=max(R[x],R[rc[x]]),U[x]=min(U[x],U[rc[x]]),D[x]=max(D[x],D[rc[x]]);
}
int build(int l,int r)
{
	if (l>r) return 0;
	int mid=(l+r)>>1;
	double ax=0,ay=0,vx=0,vy=0;
	for (int i=l;i<=r;i++) ax+=s[i].x,ay+=s[i].y;
	ax/=(double)(r-l+1),ay/=(double)(r-l+1);
	for (int i=l;i<=r;i++) vx+=sq(ax-s[i].x),vy+=sq(ay-s[i].y);
	if (vx>=vy) d[mid]=1,nth_element(s+l,s+mid,s+r+1,cmp1);
	else d[mid]=2,nth_element(s+l,s+mid,s+r+1,cmp2);
	lc[mid]=build(l,mid-1);rc[mid]=build(mid+1,r);
	maintain(mid);return mid;
}
int dis(int a,int b) {return max(sqr(L[a]-s[b].x),sqr(R[a]-s[b].x))+max(sqr(U[a]-s[b].y),sqr(D[a]-s[b].y));}
void query(int l,int r,int x)
{
	if (l>r) return;
	int mid=(l+r)>>1;int t=sqr(s[x].x-s[mid].x)+sqr(s[x].y-s[mid].y);
	if (t>(que.top())) {que.pop();que.push(t);}
	if (l==r) return;
	int disl=dis(lc[mid],x),disr=dis(rc[mid],x);
	if (disl>que.top()&&disr>que.top())
	{
		if (disl>disr) {query(l,mid-1,x);if (disr>que.top()) query(mid+1,r,x);}
		else {query(mid+1,r,x);if (disl>que.top()) query(l,mid-1,x);}
	}
	else {if (disl>que.top()) query(l,mid-1,x);if (disr>que.top()) query(mid+1,r,x);}
}
signed main()
{
	freopen("farthest.in","r",stdin);
	freopen("farthest.out","w",stdout);
	n=read();k=read()*2;
	for (int i=1;i<=k;i++) que.push(0);
	for (int i=1;i<=n;i++) s[i].x=read(),s[i].y=read();
	build(1,n);
	for (int i=1;i<=n;i++) query(1,n,i);
	printf("%lld",que.top());
	return 0;
}