萌新K-DTree 10分 #2~10WA求大佬帮调

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005,inf=0x3f3f3f3f3f3f3f3f;
int n,root,m,lst,top,tot,WD,ans=inf,Ans=inf,ans2;
double alpha=0.75;
struct Point {
	int x[2];
	Point(int x0 = 0,int x1 = 0){
		x[0] = x0;x[1] = x1;
	}
	bool operator != (const Point &_o) const{
		return (_o.x[0]!=x[0])||(_o.x[1]!=x[1]);
	}
}tmp[N];
int rub[N];
struct node {
	int l,r,d,siz;
	int mi[2],ma[2];
	Point tp;
} kt[600005];
int newnode(){
	if(top) {
		kt[rub[top]]=(node){0,0,0,0,0,0,0,0,Point()};
		return rub[top--];
	}
	else return ++tot;
}
bool operator < (Point a,Point b) {
	return a.x[WD]<b.x[WD];
}
void TtoL(int x,int &count) { //Tree to Line 即把树上数据存在序列中
	if(!x) return;
	if(kt[x].l) TtoL(kt[x].l,count);//递归存储左子树
	tmp[++count]=kt[x].tp;//存储当前节点
	rub[++top]=x;
	if(kt[x].r) TtoL(kt[x].r,count);//递归存储右子树
	return;
}
void update(int x) {
	int &ls=kt[x].l,&rs=kt[x].r;
	kt[x].siz=kt[ls].siz+kt[rs].siz+1;
	for(int W=0;W<=1;W++) {
		kt[x].mi[W]=kt[x].ma[W]=kt[x].tp.x[W];
		if(ls) kt[x].mi[W]=min(kt[x].mi[W],kt[ls].mi[W]),kt[x].ma[W]=max(kt[x].ma[W],kt[ls].ma[W]);
		if(rs) kt[x].mi[W]=min(kt[x].mi[W],kt[rs].mi[W]),kt[x].ma[W]=max(kt[x].ma[W],kt[rs].ma[W]);
	}
}
int build(int l,int r,int wd) {
	if(l>r)return 0;
	if(l==r) {int x=newnode();kt[x].tp=tmp[l];update(x);return x;}
	int mid=l+r>>1,x=newnode();
	WD=wd,nth_element(tmp+l,tmp+mid,tmp+r+1),kt[x].tp=tmp[mid];
	kt[x].l=build(l,mid-1,wd^1),kt[x].r=build(mid+1,r,wd^1);
	update(x);return x;
}
void rebuild(int &x,int wd) {
	if(alpha * kt[x].siz > (double)max(kt[kt[x].l].siz,kt[kt[x].r].siz)) return;
	int count=0;
	TtoL(x,count);//先打散
	x=build(1,count,wd);//再重构
	return;
}
void insert(int &x,Point v,int wd) {
	if (!x) {
		x = newnode();
		kt[x].tp=v;
		update(x);
		return;
	}
	rebuild(x,wd);
	if(kt[x].tp.x[wd]<v.x[wd]) insert(kt[x].r,v,wd^1);
	else insert(kt[x].l,v,wd^1);
	update(x);
}
int dis(Point a,Point b){
	int res=0;
	for(int W=0;W<=1;W++) res+=(a.x[W]-b.x[W])*(a.x[W]-b.x[W]);
	return res;
}
int f(Point a, int b) {
	node &o=kt[b];
	int res=0;
	for(int W=0;W<=1;W++) {
		if(o.mi[W]>a.x[W]) res+=(o.mi[W]-a.x[W])*(o.mi[W]-a.x[W]);
		if(o.ma[W]<a.x[W]) res+=(a.x[W]-o.ma[W])*(a.x[W]-o.ma[W]);
	}
	return res;
}
void query(int x,Point u){
	if(!x) return;
	if(kt[x].tp!=u) ans=min(ans,dis(kt[x].tp,u));
	if(!(kt[x].l+kt[x].r)) return;
	int disl=kt[x].l?f(u,kt[x].l):inf,disr=kt[x].r?f(u,kt[x].r):inf;
	if(disl<disr){
		if(disl<ans) query(kt[x].l,u);
		if(disr<ans) query(kt[x].r,u);
	}else{
		if(disr<ans) query(kt[x].r,u);
		if(disl<ans) query(kt[x].l,u);
	}
}
int f2(Point a, int b) {
	node &o=kt[b];
	int res=0;
	for(int W=0;W<=1;W++) {
		res+=max((o.mi[W]-a.x[W])*(o.mi[W]-a.x[W]),(a.x[W]-o.ma[W])*(a.x[W]-o.ma[W]));
	}
	return res;
}
void query2(int x,Point u){
	if(!x) return;
	ans2=max(ans2,dis(kt[x].tp,u));
	if(!(kt[x].l+kt[x].r)) return;
	int disl=kt[x].l?f2(u,kt[x].l):-1,disr=kt[x].r?f2(u,kt[x].r):-1;
	if(disl>disr){
		if(disl>ans2) query(kt[x].l,u);
		if(disr>ans2) query(kt[x].r,u);
	}else{
		if(disr>ans2) query(kt[x].r,u);
		if(disl>ans2) query(kt[x].l,u);
	}
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	int opt=0,xx,yy,vv;
	for(int i=1;i<=n;i++){
		cin>>xx>>yy;
		insert(root,Point(xx,yy),0);
	}
	for(int i=1;i<=n;i++){
		ans=inf,ans2=-1;
		query(root,Point(xx,yy)),query2(root,Point(xx,yy));
		Ans=min(ans2-ans,Ans);
	}
	cout<<Ans;
}