计算几何基础：点、向量与直线的数据结构与运算

"基本数据结构在ACM竞赛中的应用，特别是在计算几何领域的使用" 在ACM（国际大学生程序设计竞赛）中，计算几何是一个重要的领域，涉及到多种基本数据结构和算法。点和向量是最基础的数据结构之一。在这个场景下，`struct point_t` 用于表示二维空间中的点，它由两个整数坐标 `x` 和 `y` 组成。由于多数题目输入是整数点，但在计算过程中需注意数据类型的使用，通常会用到浮点数以处理精度问题。 精度问题在计算几何中至关重要。为了避免浮点误差导致的误判，可以定义一个常量 `const EPS = 1E-6`，然后通过宏 `#define is0(x)(-EPS<(x)&&(x)<EPS)` 来判断一个浮点数是否接近于零。选择合适的 `EPS` 值是一个需要考虑的问题。此外，常量 `const PI = acos(-1.0)` 用于表示圆周率，推荐使用 `double` 类型以确保精度。 向量的运算是计算几何中的核心部分。向量的加法和减法是简单的坐标对应相加或相减，而乘法（标量乘法）则是将一个标量与向量的每个分量相乘。点积 `(x1, y1)·(x2, y2) = x1x2 + y1y2` 可以反映向量之间的角度关系，其值为正表示两个向量夹角为锐角，为零表示共线，为负表示钝角。叉积（向量积）在二维空间中是一个实数，计算公式为 `x1y2 - x2y1`，其正负可以判断两个向量构成的平行四边形的旋转方向，以及两向量是否垂直。 计算向量的幅角时，应尽量避免直接计算角度，可以通过象限判断和外积来比较两个向量的相对大小。如果需要计算具体角度，可以使用 `atan2(y, x)` 函数，其返回值范围是 `(-pi, pi]`。外积在计算几何中有广泛的应用，如判断三点的拐向、计算三角形和凸多边形的面积、判断点与线、线段、多边形的关系，以及检测线段是否相交等。 判断两线段是否相交通常通过排斥实验和跨立实验两种方法。对于线段的表示，可以定义 `struct line_t`，包含参数 `a, b, c` 来表示直线 `ax + by + c = 0`，也可以通过归一化处理使 `a` 或 `b` 始终为1，但使用整数表示直线通常更为方便，尤其是在处理整数输入的题目时。 推荐的练习题目包括 POJ1066（线段相交）、POJ1654（多边形求面积）、POJ1127（线段相交与并查集）、POJ2318（点在凸多边形内）、POJ2653（线段相交）以及 POJ1410（线段与矩形相交），这些题目可以帮助初学者熟悉计算几何的基本概念和方法。 在ACM的计算几何中，理解并熟练运用基本数据结构和算法是解决问题的关键。这包括正确处理精度、理解和运用向量运算、以及灵活应用外积等方法来解决各种几何问题。通过不断练习和学习，参赛者可以提高解决复杂计算几何问题的能力。