平面最近点对的算法实现
平面最近点对的算法实现
O(nlogn)
平面最近点对是在谈到归并算法时常用的例子,其复杂度可以到达优秀的\(O(nlogn)\);但当真正去实现这样的复杂度实际并不显然。
算法核心思想:
- 对点集按照\(x\)坐标排序
- 分成两部分\(S\),\(Q\);分别求这两部分的最近点对,假设为\(minl\)
- 进行
merge
,主要考虑距离中点横坐标距离不超过\(minl\)的点集\(M\),最坏情况下\(M\)集合大小是\(O(n)\);但我们只需对集合中每个元素元素比较8次(落在固定大小矩形上的点).所以复杂度\(O(nlogn)\)
实现问题:
如何找到所需要比较的8个元素?
就我翻阅的资料来看,还没有真正常数时间就能找到这8个元素的实现,所以很多实现的最坏情况的复杂度是\(O(n^2)\)(也许均摊情况会好很多).
这里给出\(O(nlognlogn)\)的算法;
思想:找到\(M\)集合元素后,按照\(y\)轴进行排序,这样只需向上比较8个点即可(常数个点)
复杂度分析:
\(f(n) = 2f(n/2)+O(nlogn)\)
master thereom:
\(O(nlogn^{k+1}) = O(nlognlogn)\)
例题:hdu1007
code```cpp/* * @Author: fridayfang * @Github: https://github.com/fridayfang * @LastEditors : fridayfang * @Date: 2020-01-06 19:09:57 * @LastEditTime : 2020-01-06 20:57:53 */#includeusing namespace std;#define mm(a,b) memset(a,b,sizeof(a))#define db(x) cout selec;struct point{ double x,y; point(){} point(double _x,double _y){x=_x,y=_y;}}ps1[maxn],ps2[maxn];bool cmp1(const point& p1, const point&p2){ if(p1.x>1; double leftd = getn(l,mid); double rightd = getn(mid+1,r); double mm = min(leftd,rightd); // db(mm); mm = min(mm, _merge(l,mid,r,mm)); // db(l);db(r);db(mm); return mm; }double solve(){ return getn(0,n-1); }int main(){ // fast(); while(~scanf("%d",&n)&&n){ for(int i=0;i>ps1[i].x>>ps1[i].y; ps2[i].x = ps1[i].x; ps2[i].y = ps1[i].y; } sort(ps1,ps1+n, cmp1); sort(ps2,ps2+n, cmp2); printf("%.2lf\n",solve()/2.0); }}```相关推荐
kls00 2020-09-20
美丽的泡沫 2020-09-08
wonner 2020-06-17
ldh 2020-06-09
算法改变人生 2020-06-03
lickylin 2020-05-27
aaJamesJones 2020-05-20
baike 2020-05-14
Cypress 2020-05-09
roseying 2020-02-23
waitwolf 2020-02-21
JavaWDB 2020-02-03
dbhllnr 2020-02-02
yuanlunxi 2019-12-05
ustbfym 2019-12-04
lixiaotao 2019-11-10
TTdreamloong 2019-10-30
whtqsq 2019-09-08
LinuxAndroidAI 2015-04-15