• 2024-08-14【算法模板】计算几何:旋转卡壳求凸包直径
    旋转卡壳算法是一种几何算法,主要用于在二维平面上求解与凸包相关的最优问题。该算法利用凸包顶点的顺序性和对称性,通过模拟两个卡壳(calipers)沿着凸包边界的旋转来寻找最优解。常见的应用包括计算凸包的直径(即最远点对之间的距离)、最小包围矩形(最小面积矩形),以及最小宽度(宽度
  • 2024-07-23Andrew 算法求凸包
    Andrew算法求凸包参考资料:右手定则(baidu.com)内积和外积-OIWiki(oi-wiki.org)\(a\)与\(b\)相对位置\(b\)在\(a\)的逆时针方向:\(a\timesb>0\)顺负逆正(其实就是高中数学对于正负角的定义)凸包-OIWiki(oi-wiki.org)排序后最小和最大的元素为什么一