Graham's算法

根据给定的信息，我们可以深入探讨Graham's算法及其在该代码中的实现细节。Graham's算法是一种用于寻找二维平面上给定点集的凸包的经典算法。凸包问题是指找到一个包含所有点的最小凸多边形。Graham's算法通过一系列几何计算来实现这一目的。 ### Graham's算法概述 Graham's算法主要分为以下几个步骤： 1. **选择最下最左的点**：在所有点中找到坐标值最小的点（即最下最左的点），这个点必定属于凸包。 2. **排序其他点**：按照极角大小对其他点进行排序。这里通常会用到`atan2`函数来计算极角，然后按升序排列。 3. **构建凸包**：从最下最左的点开始，按照排序后的顺序遍历各个点，并利用向量叉积判断当前三点是否构成左转。如果不是，则去除栈顶元素，直到形成左转为止；之后将当前点压入栈中。 ### 代码解读 接下来，我们具体分析代码中的实现细节。 #### 定义结构体与常量 首先定义了一个`point`结构体，包含每个点的x、y坐标以及其极角值`thera`。此外还定义了常量`PI`表示圆周率π。 ```cpp struct point { double x, y; double thera; }; ``` #### 排序函数 代码中定义了两个比较函数`cmp1`和`cmp2`，分别用于对点进行初步排序和极角排序。 - `cmp1`用于将所有点按照y坐标从小到大排序，若y坐标相同，则按照x坐标从小到大排序。这一步确保了最下最左的点被选为起点。 - `cmp2`用于按照极角从小到大排序，如果极角相同，则按x坐标从小到大排序。 ```cpp bool cmp1(point a, point b) { if (a.y == b.y) return a.x < b.x; return a.y < b.y; } bool cmp2(point a, point b) { if (a.thera == b.thera) return a.x < b.x; else return a.thera < b.thera; } ``` #### 计算极角与距离 `get_thera`函数用于计算点相对于另一个点的极角，使用`atan2`函数实现。 ```cpp double get_thera(point a0, point a1) { return atan2((a1.y - a0.y), (a1.x - a0.x)); } ``` `dist_2point`函数用于计算两点之间的欧几里得距离。 ```cpp double dist_2point(point a1, point a2) { return sqrt((a1.x - a2.x) * (a1.x - a2.x) + (a1.y - a2.y) * (a1.y - a2.y)); } ``` #### 凸包构建 `line_3point`函数用于判断三个点是否构成左转或右转。如果构成左转，则返回`false`；如果构成右转，则返回`true`；如果三点共线，则根据具体情况决定返回值。 ```cpp bool line_3point(point a1, point a2, point a3) { double P = (a2.x - a1.x) * (a3.y - a1.y); double Q = (a3.x - a1.x) * (a2.y - a1.y); double M = P - Q; if (M > 0) return false; if (M < 0) return true; if (M == 0) return true; return false; } ``` 在主函数`main`中，首先读取输入数据，包括点的数量和半径`r`。然后按照Graham's算法的步骤进行操作： 1. 对所有点进行初步排序，找出最下最左的点。 2. 计算各点相对于最下最左点的极角，并进行排序。 3. 使用栈结构构建凸包，依次加入满足条件的点。 4. 最后计算凸包周长，并加上圆弧长度，得到最终结果。 这段代码实现了Graham's算法的基本流程，通过对点集进行排序和筛选，有效地找到了构成凸包的点集。这对于理解并应用Graham's算法解决实际问题非常有帮助。