分治求 二维平面内最近两个点的距离

在平面内有两个点找出最近的两个点。

分析： 如果我们将平面一份为二，那么这个答案可能来自三种情况。 1.这两个点在左半平面。 2.这两个点在右半平面。 3.这两个点横跨左右平面分割线。 那么我们需要先把第一二种情况下得到的答案求出（假设为d），而这个问题就是原来问题的一个子问题，可以使用递归求解。然后再处理离分割线左侧d和离右侧d的所有点，将这些点按y坐标排序，从第一个开始遍历（两层循环），每次判断两点的纵距离是否大于d，是则break；

另外，平面一份为二，尽量均匀分布，所以可以先以x坐标排序，然后注意递归终点。

代码：

#include <bits/stdc++.h>

using namespace std;

int n;
struct node
{
          
   
    int x, y;
}ar[100050];
int br[100050];

//用于求两点间距离
double dis(struct node a, struct node b)
{
          
   
    double x = (double)(a.x - b.x) * (a.x - b.x);
    double y = (double)(a.y - b.y) * (a.y - b.y);
    return (double)sqrt(x + y);
}

bool cmp1(struct node a, struct node b)
{
          
   
    return a.x < b.x;
}

bool cmp2(int a, int b)
{
          
   
    return ar[a].y < ar[b].y;
}

double near_dis(int l, int r)
{
          
   
    //两个递归终点，只剩两个点或三个点时，两两求距离然后取min
    if(r == l + 1)  return dis(ar[l], ar[r]);
    if(l + 2 == r)  return min(dis(ar[l], ar[r]), min(dis(ar[l], ar[l + 1]), dis(ar[l + 1], ar[r])));
    //分割，求出情况1， 2的结果
    int mid = (l + r) >> 1;
    double ans = min(near_dis(l, mid), near_dis(mid + 1, r));
    //找出符合条件的点，并将其按y坐标排序
    int cnt = 0;
    for(int i = l; i <= r; ++i)
    {
          
   
        if(ar[i].x >= ar[mid].x - ans && ar[i].x <= ar[mid].x + ans)
            br[++cnt] = i;
    }
    sort(br + 1, br + cnt + 1, cmp2);
    //求出情况2的答案，不断取min更新
    for(int i = 1; i <= cnt; ++i)
    {
          
   
        for(int j = i + 1; j <= cnt; ++j)
        {
          
   
            if(ar[br[j]].y - ar[br[i]].y >= ans)    break;
            ans = min(ans, dis(ar[br[i]], ar[br[j]]));
        }
    }
    return ans;
}

int main()
{
          
   
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d%d", &ar[i].x, &ar[i].y);
    sort(ar + 1, ar + n + 1, cmp1);//按x排序
    cout << near_dis(1, n) << 
;
    return 0;
}