计算几何：Minkowski和与凸多边形求和

"Minkowski和的算法是计算几何领域中的一个重要概念，主要应用于处理凸多边形的求和问题。在ACM竞赛中，掌握这个算法对于解决几何类问题至关重要。该算法处理的是两个逆时针方向的凸多边形A和B的求和，即将它们的边视为向量，进行极角排序后首尾相连，得到的结果是新的凸多边形。" 在计算几何中，我们通常使用简单数据结构来表示点和向量。例如，可以定义一个名为`point_t`的结构体，包含两个整数变量`x`和`y`，既可作为点的坐标，也可作为向量的分量。需要注意的是，虽然输入通常是整点，但在计算过程中应考虑浮点数的精度问题。为了避免浮点误差导致的问题，可以定义一个很小的常量`EPS`（如1E-6），用于判断近似等于零的情况。 向量的运算包括加法、减法和标量乘法。点积（内积）是向量之间的一种关键运算，表示两向量的投影乘积，计算公式为`(x1, y1)·(x2, y2) = x1x2 + y1y2`。而叉积（外积）在二维空间中表示为一个实数，它代表两个向量构成的平行四边形的面积，计算公式为`x1y2 - x2y1`。叉积的符号还能够指示两个向量之间的夹角是顺时针还是逆时针，以及夹角的正负。 在处理向量和角度时，应尽量避免直接计算角度，因为这可能引入不必要的精度问题。如果确实需要角度值，可以使用`atan2(y, x)`函数，其值域为`(-π, π]`。外积在计算几何中有广泛的应用，比如判断三点的拐向、求三角形和凸多边形的面积、点是否在线上或多边形内，以及线段相交等问题。 线段相交的判断通常通过排斥实验和跨立实验来进行。对于线段的数据结构，可以定义一个`line_t`结构体，包含三个浮点数`a`, `b`, `c`来表示直线方程`ax + by + c = 0`。为了简化处理，有时会将直线方程归一化，确保`a`或`b`始终为1，但最好的做法是使用整数表示直线，尤其是当输入数据为整点时。 以下是一些涉及这些概念的POJ题目： - POJ1066：线段相交 - POJ1654：多边形求面积，适合初学者 - POJ1127：线段相交与并查集 - POJ2318：判断点是否在凸多边形内，适合初学者 - POJ2653：线段相交，适合初学者 - POJ1410：线段与矩形相交 Minkowski和的算法在处理凸多边形的组合问题时提供了有效的解决方案，而计算几何中的其他基础概念如点、向量、直线及其运算，对于理解和解决这类问题同样至关重要。通过熟练掌握这些基础知识，可以更高效地解决ACM竞赛中的计算几何问题。