【文件属性】:
文件名称:分治法解决凸包问题(C语言实现)
文件大小:1KB
文件格式:RAR
更新时间:2017-06-17 13:26:32
凸包 分治法 C
先预排序,预排序后最左和最右的点肯定是凸包中的点。然后可以递归的从内向外扩展凸包,在当前直线的2侧寻找最高点,最高点肯定在凸包中,这里涉及到一些数学知识:
a,首先定义射线p1到p2的左侧:若p1 p2 p构成的顺序是逆时针,称p在射线的左侧
b,三角形p1 p2 p3的面积等于下列行列式的一半:
仅当p3在射线p1p2左侧时这个值才为正。
由此我们很容易求p1,p2左侧的最高点(离直线最远的点,这个点即凸包向外扩展得到的新顶点),得到一个最高点后,就得到了2条新边,继续向外扩展
【文件预览】:
tubao.cpp
input.txt
网友评论
- 谢谢!帮助很大!
- 不能用啊!!!!!!!!!!!!!!!程序停止运行!凸包问题是排序吗!!!!!!!!!!!!!!!!!!!
- 感谢你的分享,真的很有帮助
- 代码错误,C++
- 有溢出的问题
- 为什么改变输入数组的大小,就老是错误呀
- 代码的注释比较齐全
- 非常实用代码
- 感谢你的分享,真的很有帮助
- 很不错,比较容易理解~