首页 > 代码库 > 平面最近点对(分治nlogn)
平面最近点对(分治nlogn)
平面最近点对,是指给出平面上的n个点,寻找点对间的最小距离
首先可以对按照x为第一关键字排序,然后每次按照x进行分治,左边求出一个最短距离d1,右边也求出一个最短距离d2,那么取d=min(d1, d2)
然后只需考虑横跨左右两侧的点,不妨枚举左侧的点pi
那么很显然的是如果pi距离中间的点超过了d,便可以直接舍去,只需考虑距离中间点小于d的点
这样一来就可以对每个pi画一个边长为2d的正方形,易证,矩形内最多存在8个点。
那么关键问题就是要快速找这8个点
朴素做法是对分治后的点进行快排,这样复杂度就是nlognlogn
但是我们如果结合归并排序,每一次分治的过程顺带就按y归并排序,便可以把logn省掉了 (%%%想出做法的和鑫神犇)
代码如下
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; struct P { int x, y; bool operator <(const P& B)const { return x < B.x; } }p[100050]; int dis(P &A, P &B) { return (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y); } P Q[100050]; int Divide(int l, int r) { if(l == r) return 1e7; int mid = (l+r)>>1, d, tx = p[mid].x, tot = 0; d = min(Divide(l, mid), Divide(mid+1, r)); for(int i = l, j = mid+1; (i <= mid || j <= r); i++) { while(j <= r && (p[i].y > p[j].y || i > mid)) Q[tot++] = p[j], j++; //归并按y排序 if(abs(p[i].x - tx) < d && i <= mid) //选择中间符合要求的点 { for(int k = j-1; k > mid && j-k < 3; k--) d = min(d, dis(p[i], p[k])); for(int k = j; k <= r && k-j < 2; k++) d = min(d, dis(p[i], p[k])); } if(i <= mid) Q[tot++] = p[i]; } for(int i = l, j = 0; i <= r; i++, j++) p[i] = Q[j]; return d; } int main() { int n; cin>>n; for(int i = 1; i <= n; i++) cin>>p[i].x>>p[i].y; sort(p+1, p+1+n); cout<<Divide(1, n)<<endl; }
注意:这里只选了坐标为整数的点,而且范围较小,需要一定的更改才能使用
平面最近点对(分治nlogn)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。