给定一个数组 trees
,其中 trees[i] = [xi, yi]
表示树在花园中的位置。
你被要求用最短长度的绳子把整个花园围起来,因为绳子很贵。只有把 所有的树都围起来,花园才围得很好。
返回恰好位于围栏周边的树木的坐标。
示例 1:
输入: points = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]] 输出: [[1,1],[2,0],[3,3],[2,4],[4,2]]
示例 2:
输入: points = [[1,2],[2,2],[4,2]] 输出: [[4,2],[2,2],[1,2]]
class Solution {
public:vector<vector<int>> outerTrees(vector<vector<int>>& trees) {// 如果树的数量小于等于 1,直接返回if (trees.size() <= 1) return trees;// 自定义比较函数auto cmp = [](vector<int>& p1, const vector<int>& p2) {return p1[0] < p2[0] || (p1[0] == p2[0] && p1[1] < p2[1]);};sort(trees.begin(), trees.end(), cmp);// 构建下凸包vector<vector<int>> lower;for (auto& tree : trees) {while (lower.size() >= 2 && cross(lower[lower.size() - 2], lower.back(), tree) < 0) {lower.pop_back();}lower.push_back(tree);}// 构建上凸包vector<vector<int>> upper;for (int i = trees.size() - 1; i >= 0; i--) {auto& tree = trees[i];while (upper.size() >= 2 && cross(upper[upper.size() - 2], upper.back(), tree) < 0) {upper.pop_back();}upper.push_back(tree);}vector<vector<int>> result(lower);result.insert(result.end(), upper.begin(), upper.end());set<vector<int>> res(result.begin(), result.end());// 去掉重复的点return vector<vector<int>>(res.begin(),res.end());//返回vector<vector<int>>类型}// 计算叉积int cross(vector<int>& O, vector<int>& A, vector<int>& B) {return (A[0] - O[0]) * (B[1] - O[1]) - (A[1] - O[1]) * (B[0] - O[0]);}
};
auto cmp = [](vector<int>& p1, const vector<int>& p2) {
return p1[0] < p2[0] || (p1[0] == p2[0] && p1[1] < p2[1]);
};
这个比较函数用于根据树木的位置对它们进行排序。首先按 x 坐标排序,如果 x 坐标相同,则按 y 坐标排序。
叉积 A×B=Ax⋅By−Ay⋅Bx 可以帮助判断三点之间的相对方向。给定三点 O(原点)、A 和 B,叉积的结果可以用来判断 A 和 B 相对于 O 的位置关系:
- 正数:表示 B 在 A 的左侧,形成的角度是逆时针(O -> A -> B 是一个左转)。
- 负数:表示 B 在 A 的右侧,形成的角度是顺时针(O -> A -> B 是一个右转)。
- 零:表示 A 和 B 在同一条直线上。
构建凸包:
while (lower.size() >= 2 && cross(lower[lower.size() - 2], lower.back(), tree) < 0)
构建下凸包时,必须要保证有至少两个点,才能进行三点之间的相对方向判断。while
循环可以确保我们在引入每一个新点时,能够动态地调整 lower
中的点,以确保所有点都能形成一个外包围的凸形结构。
举个例子:第一个点 [1, 1]
:
加入 lower
,当前 lower = [[1, 1]]
第二个点 [2, 0]
:
加入 lower
,当前 lower = [[1, 1], [2, 0]]
第三个点 [3, -1]
:
现在 lower.size() == 2
,计算叉积:
cross([1, 1], [2, 0], [3, -1])
:
(2 - 1) * (-1 - 1) - (0 - 1) * (3 - 2) = 1 * (-2) - (-1) * 1 = -2 + 1 = -1
叉积为负数,说明这三个点构成了 顺时针方向,这通常意味着形成了一个凹形。因此,进入 while
循环,移除 [2, 0]
,然后再将 [3, -1]
加入 lower
。
lower
最终包含的是所有位于下边界上的点,这些点构成了围绕给定树木坐标的下半部分的凸包。具体来说,lower
会包含从最左侧的点到最右侧的点,形成一个向上的弯曲结构。
upper
构建上凸包。代码的逻辑与构建下凸包的过程相似,但它从树木坐标的最后一个点开始逆序遍历,直到第一个点。
最后将将 lower
和 upper
两个 vector
合并为一个新的 vector
result.insert(result.end(), upper.begin(), upper.end());
result.end()
表示插入的位置是result
的末尾。upper.begin()
和upper.end()
表示要插入的元素范围,即从upper
的起始位置到结束位置。
set
去重:去除upper和lower重复的部分
set<vector<int>> res (result.begin(), result.end()); 在构造过程中,set
会自动去除 result
中的重复元素,只保留唯一的元素
由于set
的返回值类型与 vector
不同。是set<vector<int>>,而我们需要的是vector<vector<int>>,所以最后
return vector<vector<int>>(res.begin(),res.end());