平面最近点（加强）_(分治)

原题链接：P1429 平面最近点对（加强版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：给定多个点，求最小的两点距离（x, y 都大于等于0）

思路

我看不出来可以分治做，其实是最简单的分治思想，即对空间做分治，查找最近的两点，分治成查找不同空间范围的最近两点，再比较区域交叉的位置，很像最大子段和

难的地方在分析 首先是一分二，按x（或y）排序后分成两个区域，分别求最近点，然后剩下的可能是最近点的点必然在mid的两侧，且与mid之间距离要小于已经找到的两点最短距离

这里有一步是缩小搜索空间，第三个空间局限在和mid排序方向上距离 小于 已找到最小距离d的点，对这些点做查找

代码

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 2e5 + 10, INF = 2 << 19;
 
struct S{
    double x, y;
    bool operator < (const S &w) const
    {
        return x < w.x;
    }
}S[N];
 
 
bool cmp(int a, int b)
{
    return S[a].y < S[b].y;
}
 
double dist(int a, int b)
{
    return sqrt((S[a].x - S[b].x) * (S[a].x - S[b].x) + (S[a].y - S[b].y) * (S[a].y - S[b].y));
}
 
int n;
int t[N];
 
double merge(int l, int r)
{
    double d = INF;
    if(l == r)  return d;
    else if(r - l == 1) return dist(l, r);
 
    int mid = l + r >> 1;
    double d2 = merge(l, mid),  d3 = merge(mid + 1, r);
    d = min(d2, d3);
 
    int j = 0;
    for(int i = l; i < r; i ++)
    {
        if(fabs(S[i].x - S[mid].x) < d) t[j ++] = i;
    }
 
    sort(t, t + j, cmp);
 
    for(int i = 0; i < j; i ++)
        for(int k = i + 1; k < j && fabs(S[t[i]].y - S[t[k]].y) < d; k ++)
        {
            if(i != k)
            {
                d = min(d, dist(t[i], t[k]));
            }
        }
 
    return d;
}
 
int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        cin >> S[i].x >> S[i].y;
    }
 
    sort(S, S + n);
 
    double ans = merge(0, n - 1);
 
    printf("%.4lf\n", ans);
 
    return 0;
}