题解 P1429 【平面最近点对（加强版）】

· · 题解

一道超级经典的计算几何问题，学了好久终于学明白了，这里仔细跟大家聊一下：

首先看到这个题，第一反应肯定是暴力，两重循环，求出所有的点的距离，然后再找最小值，对吧？？？

废话少说，上代码

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
struct node{
    double x;
    double y;
};
struct node point[200005];
double dis(node a,node b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>point[i].x>>point[i].y;
    }
    double minn=1<<31-1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j)continue;
            if(minn>=dis(point[i],point[j]))minn=dis(point[i],point[j]);
        }
    }
    printf("%.4lf\n",minn);
    return 0;
}

懒得加注释了，能做到这的我相信大家都能看懂，然后很高兴的提交了，于是乎： 啥玩意？超时，于是看了一下题目 然后我用了一个小时算了一下 200000*200000好像超了， 这咋做？？？？？不会了，算了不做了

于是乎，本着执着探索的精神，终于研究明白了，这道题是一道很经典的计算几何问题，叫最近点对，什么思路呢？

分治算法：

啥是分治算法？

1) 把它分成两个或多个更小的问题；
2) 分别解决每个小问题；
3) 把各小问题的解答组合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决。

说啥呢？

反正就是把大问题换成若干个相同小问题，然后将小问题解决，从而解决大问题

啥意思？ 这道题，比如说咱们要求平面中两点的最小距离，那咱们可不可以把平面分成左边和右边两半？好，那这道题变成了找左边点的最小距离和找右边点的最小距离是不是？还是不会？，那继续分呗 最终分到了每个平面只有两个点，这你总该会了吧，把每个小平面的距离算出来，然后找最小值？？？no 没这么简单， 举个栗子：

如图所示，左边最小的距离是d1，右边最小的距离是d2， 那么如果d1<d2，那最小距离就是d1嘛？显然不是，因为两个平面的交叉部分还可能有更小的距离，那怎么办？继续比较更小两个平面中间的点呗。

好，题做完了 还有点懵是不是？ 那咱们呢重新捋一下， 第一步：把题目分成两个左右两个面。 第二步：分别求出左右两个平面的最近点对 第三部：看两个平面中间的点有没有比刚才那个最近距离还近的。 题做完了 好，那现在只有第二步咱们不会是吧？ ？？？？？发现了没，第二步和题目一样吧？

是不是发现点规律了？

这就是了，分治的思想

上代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
#define Inf 1<<31-1
struct node{
    double x;
    double y;
};
struct node point[200005];
int mpt[300005];
double dis(node a,node b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));//不解释，不会自己去面壁 
}
bool cmp1(node a,node b)
{
    if(a.x==b.x)return a.y<b.y;
    return a.x<b.x;
}//第一个排序是按照x坐标排序，排序以后才好分左右平面 
bool cmp2(int a,int b)
{
    return point[a].y<point[b].y;
}//第二个排序是选择中间的点，不懂得往下看 
double run(int left,int right)
{
    int d=Inf; 
    if(left==right)return d;//如果自己和自己的距离最近，那这题就变成入门了，直接cout<<0.0000<<endl就过了。。。所以咱们把自己和自己的距离设置为正无穷 
    if(left+1==right)return dis(point[left],point[right]);//这两个点中间没有任何点，所以直接求距离就是了 
    int mid=(left+right)>>1;//如果中间还有其他点，那就再中间分开。 
    double d1=run(mid,right);//找左边的最小距离 
    double d2=run(left,mid-1);//找右边的最小距离 
    double minn=min(d1,d2);//求出两个最小距离谁更小 
    int k=0;
    for(int i=left;i<=right;i++)
    {
        if(fabs(point[mid].x-point[i].x)<=minn)
        {
            mpt[++k]=i;
        }
    }//还记得刚才讲过，有可能在两个平面中间还有其他的更小距离嘛？这个就是按照x坐标找可能出现的点 
    sort(mpt+1,mpt+k+1,cmp2);//按这些点的y坐标排序 
    for(int i=1;i<=k;i++)
    {
        for(int j=i+1;j<=k && point[mpt[j]].y-point[mpt[i]].y<=minn;j++)
        {
            if(minn>=dis(point[mpt[i]],point[mpt[j]]))
                minn=dis(point[mpt[i]],point[mpt[j]]);
        }
    }//线性扫描，找这些点的最小距离 
    return minn;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>point[i].x>>point[i].y;
    }
    sort(point+1,point+n+1,cmp1);
    printf("%.4lf",run(1,n));
    return 0;
}