最近点对问题
在与联盟的战斗中屡战屡败后，帝国撤退到了最后一个据点。依靠其强大的防御系统，帝国击退了联盟的六波猛烈进攻。 经过几天的苦思冥想，联盟将军亚瑟终于注意到帝国防御系统唯一的弱点就是能源供应。
该系统由 N 个核电站供应能源，其中任何一个被摧毁都会使防御系统失效。
将军派出了 N 个特工进入据点之中，打算对能源站展开一次突袭。不幸的是，由于受到了帝国空军的袭击，他们未能降落在预期位置。
作为一名经验丰富的将军，亚瑟很快意识到他需要重新安排突袭计划。
他现在最想知道的事情就是哪个特工距离其中任意一个发电站的距离最短。
你能帮他算出来这最短的距离是多少吗？
输入格式:
输入中包含多组测试用例。
第一行输入整数 T，代表测试用例的数量。
对于每个测试用例，第一行输入整数 N(1≤N≤100000 )。
接下来 N 行，每行输入两个整数 X(0≤X) 和 Y(Y≤1000000000)，代表每个核电站的位置的 X，Y 坐标。
再接下来 N 行，每行输入两个整数 X 和 Y，代表每名特工的位置的 X，Y 坐标。
输出格式:
每个测试用例，输出一个最短距离值，结果保留三位小数。
每个输出结果占一行。
输入样例:
在这里给出一组输入。例如：
2 4 0 0 0 1 1 0 1 1 2 2 2 3 3 2 3 3 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
输出样例:
在这里给出相应的输出。例如：
1.414 0.000
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const double INF=1e10;
const int N=100005;
int n;
struct node{
double x,y;
int flag;
bool operator < (const node &a) const{
return x<a.x;
}
}opt[N<<1],temp[N<<1];//在一段实现功能的程序中，如果要使用temp，就要先对要使用的部分进行赋值
double dis(node a,node b){//返回两点之间的距离
if(a.flag==b.flag) return INF;
return sqrt(pow(abs(a.x-b.x),2)+pow(abs(a.y-b.y),2));
}
double solve(int l,int r){// 返回排序后下标l到r这个区间中最小点距
//如果下标区间只有这一个点 返回最大值
if(l>=r) return INF;
//二分递归，求两个左右区间的最小点距，并且将小的赋给ans存储
int mid=(l+r)>>1;
double mid_x=opt[mid].x;
double ans=min(solve(l,mid),solve(mid+1,r));
//二分排序的合并过程
int left=l,right=mid+1,t=l;
while(left<=mid && right<=r){//下标区间内所有点存于temp的相同下标区间
if(opt[left].y<=opt[right].y) temp[t++]=opt[left++];
else temp[t++]=opt[right++];
}//先执行只有两个点的排序，成功比较大小；后面更多点的排序建立在其基础上：两个已排序的数列插值合并还是已排序的。
while(left<=mid) temp[t++]=opt[left++];//这两个循环只有一个能进行
while(right<=r) temp[t++]=opt[right++];
for(int i=l;i<=r;i++){
opt[i]=temp[i];
}
//从左到右将opt中的在mid_x-ans至mid_x+ans的点存进temp
//这样temp中的点既是按y排序的，又是在mid_x-ans至mid_x+ans区间里的
int k=0;
for(int i=l;i<=r;i++){
if(opt[i].x>=mid_x-ans&&opt[i].x<=mid_x+ans){
temp[k++]=opt[i];
}
}
//从有序的temp数组中 找到每个点y坐标上面不超过ans的点的点距离求出
//并且更新答案
for(int i=0;i<k;i++){
for(int j=i-1;j>=0&&temp[i].y-temp[j].y<=ans;j--){
ans=min(ans,dis(temp[i],temp[j]));
}
}
//返回这个l到r下标的最小点距
return ans;
}
int main()
{
int t;
cin>>t;
while(t--){
cin>>n;
for(int i=0;i<n;i++) {
cin>>opt[i].x>>opt[i].y;
opt[i].flag=0;
}
for(int i=n;i<n<<1;i++) {
cin>>opt[i].x>>opt[i].y;
opt[i].flag=1;
}
sort(opt,opt+(n<<1));
printf("%.3f\n",solve(0,(n<<1)-1));
}
return 0;
}
### 题解
分治、穷举、贪心？
由于题目相比普通的最近点对问题，要求出两点集间的最短距离，为避免分类可以假设不同点集的点是一个点集内距离为INF的点。距离函数dis()。
先把点按x坐标排序。在某下标区间[l,r]的solve函数也实现了该下标区间内的点转换成按y排序再储存到原处。
区间按下标区间中点mid分成两块，最近距离为\(\min\{d_左,d_右,d_{左右}\}\)。
求两边点间最短距离的贪心算法，可以只取mid点x坐标旁边的部分点满足\(mid.x-ans \leq x \leq mid.x+ans,\qquad ans=\min\{d_左,d_右\}\)。
用一般方法求出这部分点间的最小距离，就完成该步的操作，返回该下标区间内的最近距离。
递归solve得到答案。
前排支持！