题意
给出若干个点（不大于100000个），求出这些点中距离最小的两个点的距离的一半（最近点对问题）
解析
暴力解法是此类问题的一种解法，不过在这里肯定就超时了。正确的解法应该是分治算法，网上应该有很多解析。这里附上一些题解，还有关于最近点对问题的分析，下面是我对于此题AC的代码
AC代码
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#define MAX 2147483647
using namespace std;
struct Point{
double x,y;
}q[100010];
int dp[100010],n;
bool cmp(Point a,Point b){ //最开始的排序，x和y轴都从小到大
if(a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
double dis(int a,int b){ //计算两点之间的距离
return sqrt((q[a].x-q[b].x)*(q[a].x-q[b].x) + (q[a].y-q[b].y)*(q[a].y-q[b].y));
}
bool cmp2(int a,int b){ //一个重要的排序
return q[a].y < q[b].y;
}
double getClosePair(int left,int right){
if(left == right) return MAX; //这个区域只有一个点
if(left + 1 == right) return dis(left,right); //如果只有两个点，直接返回距离
int mid = (left + right)/2;
double t1 = getClosePair(left, mid); //递归求距离
double t2 = getClosePair(mid + 1, right);
double t = t1 < t2 ? t1 : t2;
int temp = 0;
for(int i = left; i <= right; i++) //筛选x轴距离小于t的
if(fabs(q[mid].x - q[i].x) <= t)
dp[temp++] = i;
sort(dp, dp + temp, cmp2); //一个重要的排序
for(int i = 0; i < temp; i++)
for(int j = i+1; j < temp && q[dp[j]].y - q[dp[i]].y < t; j++){ //筛选y轴距离小于t的
double t3 = dis(dp[i],dp[j]);
if(t3 < t) t = t3; //更新最小值
}
return t;
}
int main(){
while(cin>>n,n){
for(int i=0; i<n; i++)
cin>>q[i].x>>q[i].y;
sort(q,q+n,cmp);
cout<<fixed<<setprecision(2)<<getClosePair(0, n-1)/2<<endl;
}
}
换个思维
- 代码我相信网上多的是，我这份也不过是参考最原始的改编的而已。但是我现在有一个问题。上面的
getClosePair函数能不能改成下面这个样子
double getClosePair(int left,int right){
......
for(int i = left; i <= right; i++)
if(fabs(q[mid].x - q[i].x) <= t)
dp[temp++] = i;
//sort(dp, dp + temp, cmp2); 注意这个排序不要了
for(int i = 0; i < temp; i++)
for(int j = i+1; j < temp && fabs(q[dp[j]].y - q[dp[i]].y) < t; j++){ //注意这里的判断加上了fabs
double t3 = dis(dp[i],dp[j]);
if(t3 < t) t = t3;
}
return t;
}
- 为什么想要这样改？上面的改动是这样的，去掉了对dp数组的排序。用
fabs来控制q[dp[j]].y - q[dp[i]].y的符号。我们现在返回去看为什么要有sort(dp, dp + temp, cmp2);，这个排序，是将这块区域中的所有点按y值从小到大排序。因为j=i+1，所以j>i，所以q[dp[j]].y - q[dp[i]].y肯定是正数。难道说这个排序只是为了达到可以保持正数的效果？ - 抱着这个只是为了保证正数的想法，我去掉了
sort，加上了fabs，然后光荣WA了。
为什么？
每个程序都有它的核心代码，理解了核心代码就可以说理解了整个程序。而这个sort我觉得就是里面最妙的一笔。我用两段代码来解释为什么fabs不行
代码一：
for(int i = 0; i < temp; i++)
for(int j = i+1; j < temp && fabs(q[dp[j]].y - q[dp[i]].y) < t; j++){
double t3 = dis(dp[i],dp[j]);
if(t3 < t) t = t3;
}
代码二：
for(int i = 0; i < temp; i++)
for(int j = i+1; j < temp; j++){
if(fabs(q[dp[j]].y - q[dp[i]].y) < t){
double t3 = dis(dp[i],dp[j]);
if(t3 < t) t = t3;
}
}
这两段代码的区别就在于这个fabs的判断是放在for里面还是if里面。首先我告诉你们，代码二的换到上面的AC代码中，它的结果是对的，但是时间超了；代码一换到上面的AC代码中，它的结果是不对的。
区别我相信很多人能看出来，在for中判断，如果不满足条件，直接退出内循环，外循环的i++。如果是在for里面的if判断，则不满足条件后还会继续外循环。也就是是否退出外循环的区别。
真相只有一个
真相只有一个.jpg
在用分治法求最小距离时，我们把区域一块一块的分开，当把两块合并的时候，最小的距离是
左边那块最小的距离，右边那块最小的距离，中间部分的最小距离这三段中取最小。
左边和右边直接可以得到。在计算中间部分时我们首先求得左边那块和右边那块较小的距离t，然后在合并后的区域中，找到离合并中点的x轴距离小于t的所有的点。
for(int i = left; i <= right; i++) //筛选x轴距离小于t的
if(fabs(q[mid].x - q[i].x) <= t) //mid表示中心位置
dp[temp++] = i;
从上述得到的点中，再找出所有y轴x相对距离小于t的两点，然后这两点的距离，判断是否还小于t。换句话说，就是如果两个点的x轴相对距离和y轴相对距离都小于目前的最小距离t。则计算这两点的实际距离，判断是否小于t，如果小于则刷新t。这个过程中省去了大量的距离大的点的计算。代码如下
sort(dp, dp + temp, cmp2); //一个重要的排序
for(int i = 0; i < temp; i++)
for(int j = i+1; j < temp && q[dp[j]].y - q[dp[i]].y < t; j++){ //筛选y轴距离小于t的
double t3 = dis(dp[i],dp[j]);
if(t3 < t) t = t3; //更新最小值
}
刚才说，把fabs放在for里面的if里面也可以，但是会超时。而这就是这个sort的第二个用处。
超时主要是在内层循环中，而能及时跳出内层循环，达到剪支效果的，毫无疑问就是根据y轴排序，这样当某一点不再满足小于时，后续的点肯定也不满足。
现在想想好像是很简单……用一个 sort搞定了剪支而已。但是，我的看法就是，这个分治，最重要的地方就在于合并的最小距离处理（就像刚才，如果用fabs就是超时）。而理解了这个sort，其实也就理解了整个程序（个人看法）
网友评论