Graham's算法详解及 HDU经典题目应用

Graham's算法是一种经典且重要的计算机科学问题，尤其在几何学和计算机图形学领域有着广泛应用。这个算法主要解决的是计算凸包（Convex Hull）问题，即在一个点集中的所有点中找到最小的多边形，使得这些点都被包含在内，并且边界点恰好是点集中所有点的凸组合。题目给出的代码片段是在C++环境下实现的一个版本，用于解决这个问题。 首先，结构体`point`定义了一个二维坐标点，同时包含了一个辅助值`thera`，用于后续排序和处理。`cmp1`函数是按照点的y坐标进行升序排序，当y坐标相同时，则按x坐标降序排列，确保了对点集进行有序处理。 `cmp2`函数则是在x坐标相同的情况下，根据`thera`值进行排序，这在计算凸包的过程中可能是必要的，比如在处理三角形判定问题时，可能需要考虑一个额外的属性来确定顺序。 `get_thera`函数计算两个点之间的方向角，这对于判断点在凸包上的位置以及后续的扫描线算法（如Graham Scan）至关重要。`dist_2point`函数用于计算两点之间的欧氏距离，这是几何操作的基础。 `line_3point`函数用于判断三点是否共线，这是Graham算法中三角形检测的一部分，用来排除不在凸包内部的点。如果三个点不构成凸向量，函数会返回相应的布尔值。 `main`函数部分，通过输入n和r（可能代表点的数量和某个半径），读取点集并使用`cmp1`排序。然后，对于每个点，计算其与已排序点的交点（`thera`值），并利用这些信息构建凸包。Graham算法的核心步骤包括选择第一个点（通常是第一个非孤立点），然后每次添加下一个点，直到找到第三个点，这三个点将形成一个新的三角形，检查此三角形是否在当前凸包之外。若不在，将该点加入凸包；若在，继续选择下一个点并重复，直到遍历完整个点集。 这段代码展示了如何在HDU题目中应用Graham算法来求解一个二维点集的凸包问题。通过比较、排序、计算角度和距离，算法巧妙地确定了点的顺序和边界，从而找到了最小的凸多边形。这种算法对于计算机图形学、GIS系统和优化问题等领域具有重要意义。