### 587. Erect the Fence
题目:
难度:
Hard
思路
题目要求用一个围栏把所有的点（🌲）围起来，然后求处于围栏上点（🌲）的集合。
我们可以发现，从最左边的那个点一直往右走，只要一直都是走的逆时针方向，那么我们一定可以找到这条围栏。那么接下来就考虑最简单的情况，
- 只有两个点```p```和```q```，我们从```p```走到```q```，当```p```到原点这条直线的斜率小于```q```到原点这条直线的斜率时，```p->q```就是沿逆时针方向走的；
- 接下来考虑3个点:```p，q，r```，以```p```为参照点（即前面的原点），那么从```q```走到```r```的时候，只要```q```到```q```这条直线的斜率小于```r```到```p```这条直线的斜率，```q->r```就是沿逆时针方向走的。
因此，我们只要构建一个```orientation```函数，就可以判断出目前我们的围栏是不是沿着逆时针在走下去了。
我们用一个```stack```来存放目前认为在围栏上的点的集合，然后把所有的点按照指定规则排好序：```先按照点的x坐标升序排列，如果x相等则按照点的y坐标升序排列```。这样我们依次取点，只要```stack```里面的点大于等于```2```个我们就要无限进行判断是否走的是逆时针，如果不是就把```stack```里面最后那个点```pop```出去（可能一直```pop```到只剩一个点），否则就把目前的这个点加入到```stack```中去，因为目前它还是在逆时针方向上的。
从左往右走完一遍```points```之后，我们围栏的下部分```lower hull```就构建好了，此时我们还要构建围栏的```upper hull```，因此我们将```points```逆序一下，从右往左再来一次遍历，仍然看是否走的是逆时针。但是这次遍历我们需要进行一个判断，就是之前放进```stack```的点，此时我们还是会经过它，如果它已经在```stack```里面了，我们就不需要再加进去了，同时这样也避免了我们把最左边的点重复加进去。
```python
python
# import functools
class Solution:
def outerTrees(self, points):
"""
:type points: List[Point]
:rtype: List[Point]
"""
def orientation(p, q, r):
return (q.y - p.y)*(r.x - p.x) - (r.y - p.y)*(q.x - p.x)
# def myComparator(p,q):
# return p.x - q.x if p.x != q.x else p.y - q.y
stack= []
# points.sort(key = functools.cmp_to_key(myComparator))
points.sort(key = lambda p: (p.x, p.y))
for i in range(len(points)):
while (len(stack) >= 2 and orientation(stack[-2],stack[-1],points[i]) > 0):
stack.pop()
stack.append(points[i])
points.reverse();
for i in range(len(points)):
while (len(stack) >= 2 and orientation(stack[-2],stack[-1],points[i]) > 0):
stack.pop()
if points[i] not in stack:
stack.append(points[i])
return stack
```
简化python版本
```python
class Solution(object):
def outerTrees(self, points):
"""
:type points: List[Point]
:rtype: List[Point]
"""
def orientation(p, q, r):
return (q.y - p.y) * (r.x - q.x) - \
(q.x - p.x) * (r.y - q.y)
hull = []
points.sort(key=lambda p: (p.x, p.y))
for i in itertools.chain(xrange(len(points)), \
reversed(xrange(len(points)))):
while len(hull) >= 2 and \
orientation(hull[-2], hull[-1], points[i]) > 0:
hull.pop()
hull.append(points[i])
return list(set(hull))
```
下面是小傅大神的代码，本来想叫‘’傅神‘’的，结果这名字🤦♂️（手动捂脸）[小傅每日一题587](https://www.bilibili.com/video/av15446980/)
另外其中的```stack.pop()```这行代码注释掉也是可以的
```java
java
class Solution {
public List outerTrees(Point[] points) {
List res = new ArrayList();
Arrays.sort(points, new Comparator(){
@Override
public int compare(Point p, Point q){
return p.x == q.x ? p.y - q.y : p.x - q.x;
}
});
Stack stack = new Stack<>();
for (int i = 0; i < points.length; i++){
while(stack.size() >= 2 && orientation(stack.get(stack.size() - 2), stack.peek(), points[i]) > 0){
stack.pop();
}
stack.push(points[i]);
}
//stack.pop();
for (int i = points.length - 1; i >= 0; i--){
while(stack.size() >= 2 && orientation(stack.get(stack.size() - 2), stack.peek(), points[i]) > 0){
stack.pop();
}
stack.push(points[i]);
}
res.addAll(new HashSet<>(stack));
return res;
}
public int orientation(Point p, Point q, Point r){
return (q.y - p.y)*(r.x - p.x) - (r.y - p.y)*(q.x - p.x);
}
}
```
Author: Keqi Huang
If you like it, please spread your support
