Let's say you have a bunch of points, and you want to round them all up and calculate the area of the smallest polygon containing all of the points (nevermind why, you just want a challenge). What you're looking for is the area of the *convex hull* of these points. Here is an example, delimited in blue :



## Your task

Implement a function that will compute the area covered by the convex hull that can be formed from an array of points, the area being rounded to two decimal places. The points are given as `(x,y)`, like in an orthonormal coordinates system.

```python
points = [(0, 0), (0, 3), (4, 0)]
convex_hull_area(points) == 6.00
```

*Note* : In Python, the scipy module has a [ready made solution](https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.ConvexHull.html) for this. Of course, if you use it here, you are lame.

*P. S.* : If you enjoy this kata, you may also like this one, which asks you to compute a convex hull, without finding its area.

Difficulty: interview

Starter code:

def cross(p1,p2,p):
	

Solutions:
import numpy as np

def slope(p1, p2):
    dx, dy = vectorize(p1, p2)
    return dy/dx if dx else float("inf")

def vectorize(p1, p2):         return [b-a for a,b in zip(p1, p2)]
def getArea  (p1, p2, p3):     return np.cross(vectorize(p1, p2), vectorize(p1, p3)) / 2
def isConcave(p1, pivot, p2):  return getArea(pivot, p1, p2) >= 0

def convex_hull_area(points):
    if len(points) < 3: return 0
    
    Z = min(points)                                                                      # Leftmost point in the graph (lowest if several ones at the same x)
    q = sorted( (pt for pt in points if pt != Z),
                key = lambda pt: (-slope(pt, Z), -np.linalg.norm(vectorize(Z, pt))))     # sorted points accordingly to the slope of the line formed by "pt" and "Z" (in reversed order)
    
    hull = [Z, q.pop()]                                                                  # Construct the convex hull (Graham Scan)
    while q:
        pt = q.pop()
        while len(hull) > 1 and isConcave(hull[-2], hull[-1], pt):
            hull.pop()
        hull.append(pt)
    
    area = sum( getArea(Z, hull[i], hull[i+1]) for i in range(1, len(hull)-1) )          # Calculate area of the hull by adding the area of all the triangles formed by 2 consecutive points in the hull and having Z as summit
    return round(area, 2)

def cross(p1,p2,p):
    return (p[1] - p1[1]) * (p2[0] - p1[0]) - (p2[1] - p1[1]) * (p[0] - p1[0])
    
def dist_to(p1):
    def f(p):
        return (p1[0]-p[0]) * (p1[0]-p[0]) + (p1[1]-p[1]) * (p1[1]-p[1])
    return f

def xy_yx(p1,p2):
    return p1[0]*p2[1] - p1[1]*p2[0]
    
def convex_hull_area(pts):
    if len(pts) == 0:
        return 0
    pts = set(pts)
    new = min(pts)
    head = new
    area = 0
    while 1 :
        tail = new
        d_fn = dist_to(tail)
        new = next(iter(pts))
        for test in pts:
            if test != new and test != tail:
                c = cross(tail,new,test)
                if tail == new or c > 0: 
                    new = test
                elif c == 0 :
                    new = max(new,test,key=d_fn)
        area += xy_yx(tail, new)
        if new is head:
            return round(abs(area)/2.0,2)
    
    


from numpy import cross, subtract

def convex_hull_area(points):
    if len(points) < 3:
        return 0
    area = 0
    for direction in 1, -1:
        hull = []
        for point in sorted(points)[::direction]:
            while len(hull) > 1 and cross(*hull[-2:]) < cross(point, -subtract(*hull[-2:])):
                hull.pop()
            hull.append(point)
        area += sum(cross(hull[i-1], point) for i, point in enumerate(hull))/2
    return round(area, 2)

# Monotone chain method

def cross(a,b,o):
    return (a[0]-o[0]) * (b[1]-o[1]) - (b[0]-o[0]) * (a[1]-o[1])

def hull(pts):
    q = []
    for p in pts:
        while len(q) > 1 and cross(q[-2], q[-1], p) <= 0: q.pop()
        q.append(p)
    q.pop()
    return q

def convex_hull_area(points):
    if len(points) < 3: return 0
    points = sorted(points)
    hl = hull(points) + hull(points[::-1])
    hl.append(hl[0])
    return round(sum(x1*y2 - y1*x2 for (x1,y1),(x2,y2) in zip(hl, hl[1:])) / 2, 2)

def cross(o, a, b):
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
        
def convex_hull_area(points):
    points = sorted(points)
    
    lower = []
    for p in points:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)

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

    hull = lower[:-1] + upper[:-1]
    
    area = 0
    n = len(hull)
    j = n - 1
    for i in range(0,n): 
        area += (hull[j][0] + hull[i][0]) * (hull[i][1] - hull[j][1]) 
        j = i 
    return round(area/2.0,2)