计算几何基础：向量、精度与线段相交问题

本资源主要讲解了ACM（算法竞赛）中的计算几何基础知识，重点围绕数据结构、精度处理、向量运算及其几何意义、向量幅角计算、外积的应用以及解决特定问题的实例。以下是主要内容的详细解析： 1. 基本数据结构： 计算几何中，使用`structpoint_t`数据结构来表示点，包含整数x和y坐标，同时也被设计为向量的结构，方便处理几何操作。在实际编程中，需要注意输入整点时的数据类型处理，以防止精度损失。 2. 重要细节： - 精度问题：涉及到浮点数的精度判断，通过定义常量`EPS`（如1E-6）来判断两个数值是否接近于零。正确选择`EPS`值对算法性能至关重要。 - 使用`double`类型进行计算，减少误差，并尽量避免除法、开方、三角函数等可能导致精度问题的操作。 3. 向量运算： - 向量的基本操作包括加法、减法和乘法。其中点积计算公式为`(x1,y1)·(x2,y2)=x1x2+y1y2`，而叉积在二维中实际上是实数，表示两个向量构成的平行四边形的面积。 4. 内外积的几何意义： - 内积为负，表示两向量夹角为钝角；外积为负，指示向量间的夹角方向为顺时针，且外积可以用来计算向量之间的平行四边形面积。 5. 向量幅角计算： - 避免直接计算角度，通过比较向量的象限和外积来确定幅角大小，使用`atan2`函数处理，其值域限定在`(-pi, pi]`。 6. 外积的应用： - 外积广泛用于解决几何问题，例如判断三点的拐向、计算三角形和凸多边形的面积、以及点与几何形状的关系判断，如点在直线或线段上的位置等。 7. 相交问题： - 判断线段相交的两种方法：排斥实验和跨立实验。具体题目如POJ中的1066、1127和1410等是这类问题的经典练习。 8. 直线数据结构： - 使用`structline_t`表示直线，参数`a`, `b`, `c`分别对应直线方程`ax + by + c = 0`。在实际应用中，考虑将直线参数归一化以简化处理。 总结，这部分内容涵盖了计算几何在ACM竞赛中的一些核心概念和技术，包括数据结构设计、精度控制、向量运算及其几何含义，以及实际问题的解决方案，对于参赛者理解和解决几何类算法问题具有重要指导价值。