587 Erect the Fence

587. Erect the Fence

Hard

• 只有两个点pq，我们从p走到q，当p到原点这条直线的斜率小于q到原点这条直线的斜率时，p->q就是沿逆时针方向走的；
• 接下来考虑3个点:p，q，r，以p为参照点（即前面的原点），那么从q走到r的时候，只要qq这条直线的斜率小于rp这条直线的斜率，q->r就是沿逆时针方向走的。

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


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))


java
class Solution {
public List<Point> outerTrees(Point[] points) {
List<Point> res = new ArrayList<Point>();
Arrays.sort(points, new Comparator<Point>(){
@Override
public int compare(Point p, Point q){
return p.x == q.x ? p.y - q.y : p.x - q.x;
}
});
Stack<Point> 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]);
}
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