算法问题实战策略——15.12　常见失误与注意事项

计算几何在程序设计竞赛中比较臭名昭著的原因是，其本质上存在较多异常情况。 退化图形 设计几何算法时的常见失误是，只考虑图像的“一般位置”（general position）。一般位置指的是图形相对位置的一般情况。与其对应的异常情况称为退化（degenerate）图形，如下所示。  同一直线上的3个以上的点  相互平行或重叠的直线/线段  面积为0的多边形  多边形的边相互重叠的情况 本章介绍的代码中也考虑过这种特殊情况。确认线段相交问题中，考虑过线段平行时是重叠还是共享1个点。求凸包时，考虑过相对于当前点，最左侧的向量存在两个以上的情况（3个点处在同一直线上的情况）。 很多题目其实并不会在输入的数据中包含这些特殊情况，所以题目中没有明确表明输入数据不包含这些情况时，需要考虑自己编写的代码能否应对。 直角坐标系与屏幕坐标系 还有一个常见失误是，误将不同坐标系视为相同坐标系。本章使用的坐标系是直角坐标系，又称笛卡儿坐标系（Cartesian coordinate system）。此坐标系中，越往上y坐标值越大，越向右x坐标值越大。不过，表示数组元素位置或计算机屏幕的像素位置时，使用的屏幕坐标系其最上端的y坐标是0，越往下y值越大。虽然这种不同的表示方法并不会让问题变得更难，但会带来诸如顺时针/逆时针、左侧/右侧翻转的麻烦。因此，若要使用这种代码，就需要在接收到坐标时尽快将其变换成熟悉的坐标系上的坐标。 其他失误  令人意外的是，可以只使用整数解决许多几何问题 。解题时如果感到数值上不稳定，就应该使用整数或分数运算解决问题。  acos()、asin()、atan()等函数不仅数值上不稳定，而且非常缓慢，所以尽量不要使用。  acos()和asin()函数只接受±1范围的实数。如果发生运算误差，向函数传递了1+107左右的数值，那么函数将会返回NaN。因此，需要养成将函数输入范围限定至max(1.0, min(1.0, x))的习惯。  同样，向sqrt()函数传递0时，经常误传为很小的负数。因此，调用sqrt()函数时，应当以sqrt(max(0.0, x))这种形式限制取值范围。