自从暑假里偶然做到了 PKU 3525 之后，我就发现自己在几何题方面还有一定的欠缺。于是我又开始学了一些东西，比如 O(N × logN) 求凸包、旋转卡尺（ROTATING CALIPER）以及多边形的核等等。

    PKU 3525 是要求一个凸多边形的最大内切圆。我开始一直以为最大内切圆一定可以切在一个内角的两条边上，结果错了。图 1 就是一个反例。正确的做法应该是二分搜索圆的半径 R；对于每个 R，都把凸多边形的每条边向内平移 R，看是否还能围成一个多边形。这就要用到半平面交的方法。

    随着做了许多题目，我学到了关于凸多边形的一个很重要的规律，那就是很多 O(N²) 的搜索都可以优化成 O(N) 的。

    比如 UVA 746 就可以这样优化。这道题目要求找出两个凸多边形的两条内侧公切线，如图 2 所示。如果枚举两个多边形的任意两个顶点之间的连线，找出最左和最右的（向量方向的左右，用叉积判断），就需要 O(N²) 的时间。但是其实不用两两枚举。

    就拿找最左边的切线来说。如果已经找到了过 A 的最左边的切线（如图 3 中的红线），设那个切点为 V。那么对于另一个点，如果它在直线 AV 的右边，从它出发的最左切线的切点一定靠近 V 的逆时针方向，如图 3 中的点 B；相反，如果另一点在直线 AV 的左边，则从它出发的最左切线的切点一定靠近 V 的顺时针方向，如图 3 中的点 C。这样一来，从每一点出发，找最左切线的平均时间就降到 O(1) 了。

图 1 最大内切圆不一定切在内角上	图 2 两个凸多边形的内侧公切线
图 3 根据当前点与上一条切线的相对位置决定搜索的方向

    PKU 2079 也可以用到类似的优化。这道题是要求找出一个凸多边形上的三个顶点，使它们组成的三角形面积最大。最直接的做法是 O(N³) 的，也就是枚举所有三个顶点 i、j 和 k 的组合，但是这样太慢。观察图 4 ，当一个顶点 i 固定时，枚举顶点 j，再找出与这一对 i 和 j 形成最大三角形的 k。发现当 j 逆时针移动时（j₁ ~ j₄），k 也在逆时针移动（k₁ ~ k₄）。也就是说，每次枚举 k 的时候，只要从上一个 k 开始即可，这样搜索 k 的平均时间就降到 O(1) 了。

    但我是又加了下面一个优化才能不超时的。再观察图 4 ，当一个顶点 i 固定，另一顶点 j 按逆时针方向移动时，找到的最大三角形到最后都会逐渐变小。所以我猜测，当枚举到某一个 j，发现找到的最大三角形比上一个 j 找到的小，则基于这一个顶点 i 的搜索到此为止。我还没有想出来怎么证明这个优化是不是正确，反正我是通过了。其实我曾经似乎找到了反例，但是后来又找不到了，也就没再多想了。