平面最近点对
2022/2/5 23:43:20
本文主要是介绍平面最近点对,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
简介
平面最近点对问题即求一个平面上的 \(n\) 个点中距离最短的一对点,朴素的做法是双重循环枚举每一对点,时间复杂度为 \(O(n^2)\) ,利用归并排序的分治思想,可以将复杂度降为 \(O(n\log n)\)
原理
先将所有点按 \(x\) 坐标排序,这样我们就可以把点分成两部分,一部分在 \(mid\) 左边,另一部分在右边
那么最近点对只有三种情况:两点都在 \(mid\) 左边/两点都在 \(mid\) 右边/一点在左一点在右,前两种情况的答案可以继续分治递归得到,记为 \(d\) ,所以我们只要考虑如何求出第三种情况的最近点对 \(d_1\) ,那么最终答案就是 \(\min(d,d_1)\)
一个自然的思路是筛选出左右区间中 \(x\) 坐标距离 \(mid\) 小于 \(d\) 且 \(y\) 坐标距离小于 \(d\) 的点,因为只有这些点形成的点对距离才有可能小于 \(d\) ,再枚举这些点中的点对更新答案
这一步还有一个很强的性质:每处理一个左边的点时,右边最多只有 \(6\) 个点会被考虑到
证明:假设有 \(7\) 个点在符合范围要求,根据抽屉原理,一定会有两个点在下图的同一个小矩形中
由于这两点在同一个矩形,那么它们的距离一定小于该矩形对角线的长度,即为 \(r\sqrt{(\frac{2}{3})^2+(\frac{1}{2})^2}=\frac{5}{6}r<r=d\) 那么就不满足 \(d\) 是左区间点对的最小距离了
在归并分治的部分,我们按 \(y\) 坐标对区间内的点排序,这样最后枚举 \(y\) 坐标距离 \(mid\) 小于 \(d\) 的点时遇到不符合条件的点可以直接 break
每层分治的复杂度为 \(O(n)\) ,层数是 \(O(\log n)\) ,总复杂度是 \(O(n\log n)\)
代码
Luogu P7883
#include<bits/stdc++.h> #define ll long long using namespace std; const int MAX_N = 400000 + 5; const ll INF = 1e18; int n; struct node { ll x, y; } a[MAX_N], b[MAX_N], tmp[MAX_N]; bool cmp(node n1, node n2) { return n1.x < n2.x; } ll dis(node n1, node n2) { return (n1.x - n2.x) * (n1.x - n2.x) + (n1.y - n2.y) * (n1.y - n2.y); } ll msort(int l, int r) { if(l == r) return INF; int mid = (l + r) >> 1; ll val = a[mid].x; ll d = min(msort(l, mid), msort(mid + 1, r)); int i = l, j = mid + 1; for(int k = l; k <= r; k++) { if(j > r || (i <= mid && a[i].y < a[j].y)) b[k] = a[i++]; else b[k] = a[j++]; } for(int k = l; k <= r; k++) a[k] = b[k]; int t = 0; for(int k = l; k <= r; k++) if((a[k].x - val) * (a[k].x - val) < d) tmp[++t] = a[k]; for(int i = 1; i <= t; i++) for(int j = i + 1; j <= t && (tmp[i].y - tmp[j].y) * (tmp[i].y - tmp[j].y) < d; j++) d = min(d, dis(tmp[i], tmp[j])); return d; } int main() { scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%lld%lld", &a[i].x, &a[i].y); sort(a + 1, a + n + 1, cmp); printf("%lld\n", msort(1, n)); return 0; }
这篇关于平面最近点对的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?