0587. Erect the Fence
=====================
题目信息
--------
:题号: 0587
:难度: Hard
:主题: 平面点集、凸包、边界点、共线点
:原题: `LeetCode 0587 `_
:重点: 围住全部树、返回最外层边界上的所有点、凸包边上的共线点也必须保留、顺序不限
题目重述
--------
给定平面上若干个互不相同的整数坐标点,每个点表示一棵树。需要用一圈围栏包围所有树,返回位于最小凸包边界上的全部点坐标。
不仅凸包顶点需要返回,落在凸包边线上的共线点也属于围栏边界,必须包含在结果中。严格位于内部的点不返回;结果顺序不限。
自建示例
--------
边线上存在共线点:
.. code-block:: text
输入:trees = [[0,0],[2,0],[2,2],[0,2],[1,0],[1,1]]
输出:[[0,0],[1,0],[2,0],[2,2],[0,2]]
解释:前五个点位于矩形边界,其中 [1,0] 在底边上也必须返回;[1,1] 位于内部。
所有点共线:
.. code-block:: text
输入:trees = [[0,0],[1,1],[2,2]]
输出:[[0,0],[1,1],[2,2]]
解释:所有树都位于围栏边界上,因此全部返回。
保留共线点的单调链凸包
----------------------
按坐标排序后构造下凸壳和上凸壳。加入新点时,只有形成严格右转(叉积小于 0)才弹出中间点;叉积等于 0 的点保留,这正是题目要求的凸包边上共线树木。最后合并两条链并去重,覆盖所有点共线时的重复端点。
C++ 实现
--------
.. code-block:: cpp
class Solution {
long long cross(const std::vector& origin,
const std::vector& first,
const std::vector& second) {
return (static_cast(first[0]) - origin[0]) *
(static_cast(second[1]) - origin[1]) -
(static_cast(first[1]) - origin[1]) *
(static_cast(second[0]) - origin[0]);
}
public:
std::vector> outerTrees(
std::vector>& trees) {
std::sort(trees.begin(), trees.end());
std::vector> lower, upper;
for (const auto& point : trees) {
while (lower.size() >= 2 &&
cross(lower[lower.size() - 2], lower.back(), point) < 0) {
lower.pop_back();
}
lower.push_back(point);
}
for (auto it = trees.rbegin(); it != trees.rend(); ++it) {
while (upper.size() >= 2 &&
cross(upper[upper.size() - 2], upper.back(), *it) < 0) {
upper.pop_back();
}
upper.push_back(*it);
}
std::set> unique;
for (const auto& point : lower) unique.insert({point[0], point[1]});
for (const auto& point : upper) unique.insert({point[0], point[1]});
std::vector> result;
for (const auto& [x, y] : unique) result.push_back({x, y});
return result;
}
};
代码分析
--------
严格右转才弹出,保证边界共线点不被误删;上下链覆盖凸包两侧,集合去重只消除端点和共线遍历造成的重复,不改变返回点集合。排序耗时 ``O(n log n)``,构造与去重为 ``O(n log n)``,额外空间复杂度为 ``O(n)``。