平面内任选两个点的最小距离
讲解视频:https://www.bilibili.com/video/BV1Ax4y1v7ud/?t=4.7&vd_source=74097b9368e4f5dcefb353f0b33ef773 (不是我讲的!!)
思路:x轴(第一维)二分,找到左边min_l和右边min_r的最小距离, 再m = min(min_l, min_r),以(mid - m)和 (mid + m)为边界找到中间的最小值,比较得出最小的距离
1.
比较中间时,用一个临时数组存储符合要求的点,再按照y轴值从大到小排序,当(当前比较的点的y值)和(被比较的点的y值)的差值大于m时,可以不再比较后面的点)
2.
计算距离很快,没必要记忆化搜索
时间复杂度:约为 O(nlogn)
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
const double INF = 1e9, EIF = -1e9;
struct nd
{
double x, y;
bool operator< (const nd &w)const
{
if (x == w.x) return y < w.y;
return x < w.x;
}
}nod[N];
int tmp[N];
double dis(int a, int b)
{
double t1 = nod[a].x - nod[b].x;
double t2 = nod[a].y - nod[b].y;
return sqrt(t1 * t1 + t2 * t2);
}
bool cmp(int a, int b)
{
return nod[a].y > nod[b].y;
}
double solve(int l, int r)
{
if (l == r) return INF;
else if (l + 1 == r) return dis(l, r);
int mid = l + r >> 1;
double min_l = solve(l, mid), min_r = solve(mid + 1, r);
double m = min(min_l, min_r);
int cnt = 0;
for (int i = l; i <= r; i ++ )
if (fabs(nod[i].x - nod[mid].x) < m) tmp[cnt ++ ] = i;
sort(tmp, tmp + cnt, cmp);
for (int i = 0; i < cnt; i ++ )
for (int j = i + 1; j < cnt && (nod[tmp[i]].y - nod[tmp[j]].y < m); j ++ )
m = min(m, dis(tmp[i], tmp[j]));
return m;
}
int main( )
{
int n;
cin >> n;
double x, y;
for (int i = 0; i < n; i ++ )
{
cin >> nod[i].x >> nod[i].y;
}
sort(nod, nod + n);
printf("%.4lf", solve(0, n - 1));
return 0;
}