旋转卡壳专题总结

利用旋转卡壳的性质求解一些问题将原本  的算法优化到  .主要思维是每当找到第一个最长(最短)后,按照逆时针的顺序,都直接是下一个边或者点

1.求凸包最远距离(凸包直径) 枚举i

2.从n个点中选3个点,使得该三角形面积最大   枚举i,j  O(n^2)  因为边不一定在凸包上,可能横跨凸包

3.求最小外接矩形(求凸包最小外接矩形) 枚举i

4.求两凸包最近距离(两不相交多边形) O(max(n,m))

 

 

全部评论

相关推荐

一天代码十万三:实习东西太少了,而且体现不出你业务,3个月不可能就这点产出吧,建议实习多写点,玩具项目面试官都不感兴趣的
点赞 评论 收藏
分享
2024-12-27 10:21
已编辑
海南师范大学 媒介策划
到我怀里来:身高体重住址这些就别写了,留几个关键的就行,工作经历突出重点写详细点
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务