由于set 的返回值类型与 vector 不同。是set<vector<int>>，而我们需要的是vector<vector<int>>，所以最后 return vector<vector<int>>(res.begin(),res.end());
相关文章
- 10-12【Spring详解】Maven从安装到应用(Maven Help插件的安装)-国内源的配置(*仓库及私服的概念)-🐯🐯🐯Maven
- 10-12MySQL Spring JDBC API JdbcTemplate日期时间字段的测试使用
- 10-12C# 程序内的类数量对程序启动的影响
- 10-12【重学 MySQL】六十四、主键约束的使用-主键约束的创建
- 10-12用最短长度的绳子把整个花园围起来-输入: 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 中的重复元素，只保留唯一的元素
- 10-12掌握Razor语法：构建动态ASP.NET Core网页的基石
- 10-12关于mac下的nvm设置淘宝镜像源-1. 进入配置文件修改镜像源
- 10-12ppt压缩文件怎么压缩？压缩PPT文件的多种压缩方法
- 10-12ansible常用的模块
- 10-12java项目之科研工作量管理系统的设计与实现源码(springboot+vue+mysql)