计算几何精要：精度控制与向量运算

"这篇资料主要关注ACM竞赛中的计算几何问题，强调了精度处理、基本数据结构、向量运算以及解决几何问题的关键技巧。" 在ACM（国际大学生程序设计竞赛）中，计算几何是一门重要的领域，尤其涉及到精确计算和几何形状分析。资料中提到了几个关键知识点： 1. **精度问题**：由于浮点数计算可能出现微小误差，判断数值是否等于0时不能直接使用`==`，而是采用一个很小的阈值（如`EPS = 1E-6`）。定义`is0(x)`宏来判断一个数是否接近0，即`-EPS < x && x < EPS`。选择合适的`EPS`值至关重要，因为它直接影响算法的正确性。 2. **数据类型**：推荐使用`double`类型处理浮点数，因为它的精度较高。同时，注意在处理整点输入时，计算过程中可能需要扩展数据类型以避免精度损失。 3. **基本数据结构**：一个简单的`point_t`结构体，包含`x`和`y`坐标，可以表示点也可以表示向量。在处理计算几何问题时，合理的数据结构能简化问题。 4. **向量运算**：向量的加减乘及点积和叉积。点积表示两个向量的夹角余弦，叉积在二维空间中表现为一个实数，代表平行四边形的面积或两向量方向的相对关系。 5. **内外积的几何意义**：内积为负意味着两向量夹角为钝角，外积为负则代表顺时针方向的夹角，同时也代表面积。 6. **向量幅角计算**：尽量避免直接计算角度，可以通过向量的象限和外积来比较幅角大小。如果必须计算，使用`atan2(y,x)`函数，其值域在`(-pi, pi]`。 7. **外积的应用**：外积在解决各种几何问题中扮演重要角色，如判断拐向、计算面积、判断点的位置等。但对于非凸多边形，可能需要其他方法。 8. **两线段相交判断**：通过“排斥实验”和“跨立实验”来确定线段是否相交。 9. **题目示例**：给出了一些POJ在线编程平台上相关的计算几何题目，可以帮助练习和巩固这些概念和技巧。 10. **直线的数据结构**：可以用一个包含`a`、`b`、`c`的结构体来表示直线`ax + by + c = 0`。为了简化处理，可以将直线归一化，使`a`始终为1.0，或者在`a`为0时确保`b`为1.0。然而，对于整点输入，直接使用整数表示直线可能是更好的选择。 计算几何在ACM竞赛中涉及的问题复杂且多样化，理解并掌握上述知识点对于解决这类问题至关重要。实践这些技巧并不断进行编程训练将有助于提高解决实际问题的能力。