587.leetcode题目讲解(Python):安装栅栏(Erect the Fence)

1. 题目

题目

2. 解题思路

这道题还是比较难,需要一些背景知识(已整理到第3节中)。本题的解题思路其实是需要寻找一个点集的凸外壳,Jarvis’s 算法比较容易理解,我们从x轴最左边的点出发,寻找“最逆时针”的下一个点,直到回到最x轴左边的点,完成凸外壳的构建。

3. 背景知识

3.1 凸与非凸

凸与非凸

凸:集合中任意两点的连线在集合中
非凸:集合中存在两点,其连线不在集合中

3.2 三点方向(Orientation)

image.png

如图所示,三个有序点的方向可以分为顺时针、逆时针和共线三种。

如果(ABC)是共线,那么(CBA)也是共线,如果(ABC)是顺时针,那么(CBA)为逆时针。

3.3 方向计算

给定三点 A(x1, y1), B (x2, y2), C(x3, y3), (ABC)方向可以通过线段斜率来计算。

image.png

线段AB的斜率 :i = (y2 – y1) / (x2 – x1)
线段BC的斜率 : j = (y3 – y2) / (x3 – x3)

i < j (左图):逆时针 i > j (右图):顺时针 i = j : 共线

所以,方向 r 可以这么计算:

r > 0, 顺时针, 反之 r < 0 为逆时针,r = 0则为共线。

  1. 参考代码