题解 P6247 【[SDOI2012]最近最远点对】

\(\text{K-D Tree}\) 很简单。 ——\(\texttt{zwj}\)

Solution

一种方法是先把整棵K-D Tree建好，然后再询问每个点的最近最远点（注意剪枝），虽然可以优化建树使空间切割更平均，但是这样每对点会计算两次，常数*2。

还可以动态插点，对于每个点，先询问当前K-D Tree中的最近最远点，再插入，就能保证每对点只算一次。

不过可能出题人会卡你这种做法，我们可以玄学优化：随机化插点顺序，效果十分明显。

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,now,ls[maxn],rs[maxn],rt;
double mxx[maxn],mxy[maxn],mnx[maxn],mny[maxn],ans1=9e18,ans2;
struct node{
	double x,y;
}a[maxn];
void pushup(int u){
	mxx[u]=max(mxx[u],a[now].x);mxy[u]=max(mxy[u],a[now].y);
	mnx[u]=min(mnx[u],a[now].x);mny[u]=min(mny[u],a[now].y);
}
double sqr(double x){
	return x*x;
}
double dis(int u){
	return sqr(a[now].x-a[u].x)+sqr(a[now].y-a[u].y);
}
double mindis(int u){//子树u中最小距离
	return sqr(max(a[now].x-mxx[u],0.0)+max(mnx[u]-a[now].x,0.0))+sqr(max(a[now].y-mxy[u],0.0)+max(mny[u]-a[now].y,0.0));
}
double maxdis(int u){//子树u中最小距离
    return max(sqr(a[now].x-mxx[u]),sqr(mnx[u]-a[now].x))+max(sqr(a[now].y-mxy[u]),sqr(mny[u]-a[now].y));
}
void ins(int &u,bool op){
	if(!u)return u=now,void();
	if(!op)ins(a[now].x<=a[u].x?ls[u]:rs[u],1);
	else ins(a[now].y<=a[u].y?ls[u]:rs[u],0);
	pushup(u);
}
void askmin(int u){
    if(!u)return;
    if(u!=now)ans1=min(ans1,dis(u));
    double l=mindis(ls[u]),r=mindis(rs[u]);
    if(l<r){//剪枝：如果比答案大就不搜了
        if(l<ans1)askmin(ls[u]);
        if(r<ans1)askmin(rs[u]);
    }else{
        if(r<ans1)askmin(rs[u]);
        if(l<ans1)askmin(ls[u]);
    }
}
void askmax(int u){
    if(!u)return;
    ans2=max(ans2,dis(u));
    double l=maxdis(ls[u]),r=maxdis(rs[u]);
    if(l>r){
        if(l>ans2)askmax(ls[u]);
        if(r>ans2)askmax(rs[u]);
    }else{
        if(r>ans2)askmax(rs[u]);
        if(l>ans2)askmax(ls[u]);
    }
}
int main(){
    srand(20201213);//今天
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
        scanf("%lf%lf",&a[i].x,&a[i].y);
    random_shuffle(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        mxx[i]=mnx[i]=a[i].x;
        mxy[i]=mny[i]=a[i].y;
        now++;askmin(rt);askmax(rt);ins(rt,0);
    }printf("%.2lf %.2lf\n",sqrt(ans1),sqrt(ans2));
	return 0;
}

题解 P6247 【[SDOI2012]最近最远点对】

原文：https://www.cnblogs.com/aday526/p/solution-p6247.html