《算法技术手册》一1.3.1 贪心算法
本文共 322 字，大约阅读时间需要 1 分钟。
1.3.1 贪心算法
以下的贪心算法展示了如何找到凸包上的每个点：
- 删除P中的最低点low——low必须在凸包上。
- 垂直画一条穿过点low的直线，将剩余的n－1个点分别和点low连线，以垂直直线右侧的点的夹角为正值降序排列，夹角的范围是从90皛－90啊n-2是最右侧的点，而P0是最左侧的点。图1-3中显示了垂直线以及每个点与其的夹角。
- 以{Pn-2, low, P0}这个顺序组成的点集为基础，在剩余的点中选择可以组成凸包的点——从P1开始，将每个点尝试加至这个点集的尾部，如果这个点集的最后三个点组成的两条线段向左拐，那么就需要移除这个错误的点。
- 在访问完所有的点之后，就得到了一个凸包，如图1-3所示。
图1-3：使用贪心算法得到的凸包
转载地址：http://xuvum.baihongyu.com/
你可能感兴趣的文章
Docker源码分析（七）：Docker Container网络 （上）
查看>>
一些旁门左道
查看>>
Common Pitfalls In Machine Learning Projects
查看>>
Android内存泄漏分析及调试
查看>>
todoing
查看>>
[Cocos2d-x]Cocos2d-x 3.2 学习笔记
查看>>
进程调度
查看>>
使用代码为TextView设置drawableLeft
查看>>
Android开发（十八）——头部、中部、底部布局技巧
查看>>
Egret 集成第三方库 记录
查看>>
同源策略——浏览器安全卫士
查看>>
c/c++ 基金会(七) 功能覆盖，虚函数，纯虚函数控制
查看>>
CodeForces 484B Maximum Value
查看>>
strong vs copy
查看>>
Codeforces Round #313 (Div. 1) C. Gerald and Giant Chess DP
查看>>
基于jQuery商城网站全屏图片切换代码
查看>>
Android开发之注解式框架ButterKnife在ADT中的设置
查看>>
JAVA学习篇--Java类加载
查看>>
如何清空android ListView控件的内容
查看>>
配置SELINUX
查看>>