旋转卡壳

最近准备搞搞几何,这次拿旋转卡壳开刀,来一发学习链接:666

1. 旋转卡壳计算凸包上两点距离最大值(凸包的直径)

给出一道例题: POJ 2187

2. 旋转卡壳计算凸包宽度

3. 旋转卡壳计算点集最大三角形
计算最大面积的三角形需要三次调整夹着卡壳的平行线,定义i表示当前指的位置,定义两个指针j,k,先将调整p(i, j) 和 p(k, k + 1) 接着调整p(i, k) 和 p(j, j + 1) 最后在调整一次p(i, j) 和 p(k, k + 1),至于为什么要调整三次不妨看下这个样例:

给出一道例题:POJ 2079

4. 旋转卡壳计算两凸包最小距离
用两条直线分别围绕两个凸包的四周旋转,设两个凸包P、Q,令yminP表示P中y最小的下标,ymaxQ表示Q中y大的下标。那么不断旋转(ymaxQ, ymaxQ + 1)向量使得其和(yminP + 1, yminP)向量的叉积小于等于0,那么yminP和ymaxQ是一个对蹱点,如果此时两个向量是平行的就计算两线段的距离,如果不是平行就计算点到线段的距离。

给出一道例题:POJ 3608

5. 旋转卡壳计算两凸包最大距离

6. 旋转卡壳计算凸包最小面积外接矩形

7. 旋转卡壳计算凸包最小周长外接矩形

8. 旋转三角剖分

9. 洋葱三角剖分

10. 四边形剖分

11. 合并凸包

12. 找公切线

13. 临界切线

14. 凸多边形矢量和

15. 最薄横截带

待补全…更新中…

LEAVE A COMMENT