给出大小为n点集(p_1)，第i个点记做((x_i,y_i)),给出另外一个大小为n的点集(p_2)，记第i个点的坐标为(a_i,b_i)，现在你可以从两个点集中各选出一个点，使得两点间距离最小化，求出这个最小值，(nleq 100000)。
解
显然想到了平面最近点对，区别在于有两个点集，按照一样的方法，接下来简单讲一讲，先把两个点集合并成一个大小为(2n)的点集以后，记第i个点为((x_i,y_i,b_i))，这个三元组前两元代表坐标，后面的(b_i)表示所属点集（不妨0表示属于(p_1),1属于(p_2)）。
把所有点按照x轴坐标从小到大排序，设(d(l,r))表示处理的点编号从(lsim r)的最小值，现在考虑如何求(d(l,r))，选定一个中间点，记做(mid=l+r>>1)，然后就可以对递归下去，处理出(d(l,mid),d(mid+1,r))，对两者取min后记做(ans)。
现在的问题就变作如何求出(lsim mid)间的点和(mid+1sim r)间的点最小值，不妨将这两个点集分别记做(q_1,q_2)，注意到可以利用之前求出的ans剪枝，于是我们就只要对x轴坐标在((x_{mid}-ans,x_{mid}+ans))间的点进行处理，此时记这个由(x=x_{mid})划分成的两个点集为(w_1,w_2)，那么对于(w_1)中的每个点而言，只有(w_2)中的点能和它构成最优解，而且还要满足(w_2)中的点与该点的y轴方向上的距离不能超过ans。
因此，在最差情况下，(w_1)中的点，不妨编号记做j，点j就在(x=a_{mid})上，以它为中心可以向上延伸ans的距离，向下延伸ans的距离，向右延伸ans的距离，构成了一个长2ans,宽ans的长方形，显然里面的点最多只有6个，因为再多一个无论如何都会与它所属的点集中的一个点距离小于ans，这也不满足我们的ans为(q_1,q_2)分开来看的最小值。
因此哪怕(q_1)的点（显然夸张了）全部在(w_1)中，我们也只要对于每个点枚举至多5个点，也就是(n/2 imes 5approx n)个点，而递归只有(logn)，因此时间复杂度最好可以做到(nlog(n))。
为了便于找出一个点y方向上的满足条件的点，最自然的想法时提出(w_1,w_2)里的点，按照y轴坐标排序，然后就可以做到常数时间复杂度求最小值，也就是总时间复杂度(nlog(n)^2)。
但是注意到x方向上的排序，我们也只用了一次，也就是快速求出mid，不妨记录下mid这个点，然后递归下去，回来时按照归并排序的套路，把y轴坐标排序，然后再从左至右暴力枚举每个点可以在(w_1,w_2)中，此时得到的顺序就是y轴坐标递增的，因此我们做到了(nlog(n))。
最后注意，只有属于不同的点集(p_1,p_2)才能计算答案，一定要特判。
参考代码：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define il inline
#define ri register
#define double long double
#define Size 200050
using namespace std;
struct pos{
double x,y;bool id;
il bool operator<(const pos&a)const{
return x<a.x;
}
}p[Size],t[Size];
il double divide(int,int),dis(pos,pos);
template<class free>il free Abs(free);
template<class free>il free Min(free,free);
int main(){
int lsy;scanf("%d",&lsy);
while(lsy--){int n;scanf("%d",&n);
for(int i(1);i<=n;++i)scanf("%Lf%Lf",&p[i].x,&p[i].y),p[i].id=0;
for(int i(2*n);i>n;--i)scanf("%Lf%Lf",&p[i].x,&p[i].y),p[i].id=1;
sort(p+1,p+2*n+1),printf("%.3Lf
",divide(1,2*n));
}
return 0;
}
il double dis(pos a,pos b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
template<class free>
il free Abs(free x){
return x<0?-x:x;
}
template<class free>
il free Min(free a,free b){
return a<b?a:b;
}
il double divide(int l,int r){if(l==r)return 1e16;int mid(l+r>>1);
double mx(p[mid].x),ans(Min(divide(l,mid),divide(mid+1,r)));
int i(l),j(mid+1),k(l),tot(0);
while(i<=mid&&j<=r)
if(p[i].y<p[j].y)t[k++]=p[i++];
else t[k++]=p[j++];
while(i<=mid)t[k++]=p[i++];
while(j<=r)t[k++]=p[j++];
for(i=l;i<=r;++i)p[i]=t[i];
for(i=l;i<=r;++i)
if(Abs(p[i].x-mx)<ans)t[++tot]=p[i];
for(i=1;i<=tot;++i)
for(j=i+1;j<=tot;++j){
if(t[j].y-t[i].y>=ans)break;
if(t[i].id^t[j].id)ans=Min(ans,dis(t[i],t[j]));
}return ans;
}