Convex Hull

"""
1. Andrew's monotone chain convex hull algorithm
Input: an iterable sequence of (x, y) pairs representing the points.
Output: a list of vertices of the convex hull in counter-clockwise order, 
starting from the vertex with the lexicographically smallest coordinates.

Time Complexity: O(n log n)

Reference: 
https://en.wikibooks.org/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain

2. Perimeter of convex hull
"""
import math

def convex_hull(points):

    points = sorted(set(points))
    if len(points) <= 1:
        return points

    # 外積(根據右手定理) 

    def cross(o, a, b):
        return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
    
    # 兩向量 OA, OB, 若 OA, OB 外積為正, 則剔除 A
    upper = []
    for p in points:
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) >= 0:
            upper.pop()
        upper.append(p)


    lower = []
    for p in reversed(points):
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) >= 0:
            lower.pop()
        lower.append(p)

    return upper[:-1] + lower[:-1]

points = [(0, 4), (1, 9), (2, 6), (3, 3), (3, 8), (4, 7), (5, 0), (6, 4), (8, 7), (9, 0)]
res = convex_hull(points)
print("points:\n{}".format(points))
print("convel hull points:\n{}".format(res))

# 算周長
def dist (a, b):
    return math.sqrt(math.pow((a[0]-b[0]),2) + math.pow((a[1] - b[1]),2))
# 多附加原點在後, copy一份 list, 一份去尾, 一份去頭, 利用 map 下去算
s = res[:] + res[:1]
pm = list(map(dist, s[:-1], s[1:]))
print(sum(pm))