587. Erect the Fence
龙大恶堕了，他把自己的仁慈与软弱打包起来丢掉。
忧郁龙大已经不存在，接下来，边板与皇城就由我来统治（把头发往后梳）。
请帮龙大找出打包的方法，给你很多点，输出他们的凸包。
Example 1:
https://assets.leetcode.com/uploads/2021/04/24/erect2-plane.jpg
Input: points = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
Output: [[1,1],[2,0],[3,3],[2,4],[4,2]]
思路:
1.礼物打包问题，以前修计算几何有学过，不过忘的差不多了，只记得是用斜率算
这题范围很小可以直接记每个 x 座标上最高和最低的点
可以把上下分开算 也就是先用最高点算出上半部分的包装 再用最低点算下半部分
2.如何算上半部分就是去 iterate x 的左界和右界 从左到右加入每个 x 的最高点
如果说连续 a, b, c 三个点 线段ab斜率 < 线段bc斜率 那就是说中间的 b 会凹下去
所以最后凸包上不会有 b 这个点 这里就可以用老方法 维护一个 stack
每次有点 c 进来就检查 stack[-2] stack[-1] 和 c 的关系
如果 stack[-1] 会凹下去就 pop 掉 最后 stack 中的那些点就是凸包
3.下半部分算法类似 分开算最后再把上下半部分并在一起就好
为了不重复可以用 set 记
Python code:
class Solution:
def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:
yatx = defaultdict(list)
left, right = 101, 0
for x, y in trees:
insort(yatx[x], y)
left = min(left, x)
right = max(right, x)
def slope(a, b):
return (b[1]-a[1]) / (b[0]-a[0])
res = set()
for y in yatx[left]:
res.add((left, y))
for y in yatx[right]:
res.add((right, y))
maxstk = [(left, yatx[left][-1])]
minstk = [(left, yatx[left][0])]
for i in range(left+1, right+1):
if i in yatx:
while len(maxstk) > 1 and slope(maxstk[-2], (i, yatx[i][-1]))
< slope(maxstk[-1], (i, yatx[i][-1])):
maxstk.pop()
while len(minstk) > 1 and slope(minstk[-2], (i, yatx[i][0]))
> slope(minstk[-1], (i, yatx[i][0])):
minstk.pop()
maxstk.append((i, yatx[i][-1]))
minstk.append((i, yatx[i][0]))
res.update(maxstk)
res.update(minstk)
return list(res)