建设厅里网站查不到外地施工单位,寺庙网站建设,wordpress写博客插件,品牌建设的三大理论文章目录 平面最近点对#xff08;分治算法#xff09;Solution流程完整模板代码 平面最近点对#xff08;分治算法#xff09;
文章首发于我的个人博客#xff1a;欢迎大佬们来逛逛
平面最近点对#xff08;加强版#xff09; - 洛谷 给你一些点#xff0c;求两点之… 文章目录 平面最近点对分治算法Solution流程完整模板代码 平面最近点对分治算法
文章首发于我的个人博客欢迎大佬们来逛逛
平面最近点对加强版 - 洛谷 给你一些点求两点之间距离最小的两个点之间的最短距离。 分治算法是解决这类问题的关键。
Solution
首先将所有的点按照 x x x 为第一关键字 y y y 为第二关键字进行排序。
排序后如下
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pGAMATS2-1685532860870)(%E5%B9%B3%E9%9D%A2%E6%9C%80%E8%BF%91%E7%82%B9%E5%AF%B9%EF%BC%88%E5%88%86%E6%B2%BB%E7%AE%97%E6%B3%95%EF%BC%89%204c3ad0a0ba5c4743aed687f933a3e85a/Untitled.png)]
我们可以将所有的点分治
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7vB6twgs-1685532860871)(%E5%B9%B3%E9%9D%A2%E6%9C%80%E8%BF%91%E7%82%B9%E5%AF%B9%EF%BC%88%E5%88%86%E6%B2%BB%E7%AE%97%E6%B3%95%EF%BC%89%204c3ad0a0ba5c4743aed687f933a3e85a/Untitled%201.png)]
在这些点中我们用一条分割线来隔开如果我们一直分割则到最后 l 1 r l1r l1r 的时候就表明划分到了最后的两个点因此直接计算两个点之间的**距离**如果最后只有一个点即 l r lr lr 则我们规定此距离为无穷大。
因此我们得到两个点之间距离之后再回溯寻找相对于这两个点有没有更优的点对出现则更新继续回溯。最后结束的时候我们一定可以得到所有点的距离最短的距离。
树型图表示如下
首先递归到 [ 1 , 2 ] [1,2] [1,2] 发现此时只有 p 1 和 p 2 p1 和p2 p1和p2 两个点因此我们计算他们的最短距离假设为 3接着进入 [ 3 , 3 ] [3,3] [3,3] 此时只有一个点因此规定距离为无穷大然后我们回溯到 [ 1 , 3 ] [1,3] [1,3] 取两个孩子节点的最小值为3但是此时并没有结束我们获得的 3 只是分割线两侧分别计算的最优解我们此时还需要得到去除分割线之后的所有点的之间的最短距离更新为 p 1 和 p 3 p1 和 p3 p1和p3 之间的距离为 2.然后递归到 [ 4 , 5 ] [4,5] [4,5] 区间得到 p 4 和 p 5 p4 和 p5 p4和p5 之间距离为 2.5。然后回溯到 根节点 [ 1 , 5 ] [1,5] [1,5] 得到分割线两侧的点之间的最优解为2接着计算去除分割线之后的两点之间的最优解得到 1.2 为 p 3 和 p 4 p3 和 p4 p3和p4 之间的距离
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QEeXFBNB-1685532860871)(%E5%B9%B3%E9%9D%A2%E6%9C%80%E8%BF%91%E7%82%B9%E5%AF%B9%EF%BC%88%E5%88%86%E6%B2%BB%E7%AE%97%E6%B3%95%EF%BC%89%204c3ad0a0ba5c4743aed687f933a3e85a/Untitled%202.png)]
如何计算去除分割线之后的区间的两点的最短距离
我们称之为 跨中线处理
首先由目标区间 [ l , r ] [l,r] [l,r] 得到所有 x x x 的差值小于 d d d 的点集合。将这些点按照 y y y 值排序最后直接两两之间暴力枚举 y y y 值的差值小于 d d d 的点对距离 流程
因此我们很轻松的得到分治求平面最近点对的流程
首先将所有的点按照 x x x 和 y y y 为第一第二关键字排序。然后递归分治所有的点递归到终点时计算点的距离回溯返回局部最优解。然后计算全局最优解即跨中线处理。
时间复杂度 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)
使用归并排序会降低为 O ( n l o g n ) O(nlogn) O(nlogn) 完整模板代码
#includebits/stdc.h
#if 0#define int long long
#endifconst int N200010;
int n;
struct point{double x,y;
}A[N],B[N],T[N];
double get_dis(const point a,const point b){return std::sqrt((a.x-b.x)*(a.x-b.x)(a.y-b.y)*(a.y-b.y));
}
double solve(int l,int r){//分治if (lr){ //只有一个点return 1e9;}if (l1r){ //有两个点则算距离return get_dis(A[l],A[r]);}int midlr1;double dstd::min(solve(l,mid),solve(mid1,r)); //跨中线处理int k0;for (int il;ir;i){if (fabs(A[i].x-A[mid].x)d){B[k]A[i];}}//按照y值排序std::sort(B1,B1k,[](const point a,const point b){return a.yb.y;});for (int i1;ik;i){//枚举两个点进行距离的更新for (int ji1;jk B[j].y-B[i].yd;j){dstd::min(d,get_dis(B[i],B[j]));}}return d;
}
signed main(){std::cinn;for (int i1;in;i){std::cinA[i].xA[i].y;}//1. 按照x为第一关键字y为第二关键字排序std::sort(A1,A1n,[](const point a,const point b){if (a.xb.x) return a.yb.y;return a.xb.x;});printf(%.4lf\n,solve(1,n));return 0;
}
