#!/usr/bin/python3
 
# positive if p,q,r is counterclockwise
# negative if p,q,r is clockwise
def orientation(p,q,r):
	return ((q[0]-p[0]) * (r[1]-p[1])) - ((r[0]-p[0]) * (q[1]-p[1]))
 
def upperHull(P):
    P.sort() # Sort by x coordinate
    ch = [P[0]]
    for p in P[1:]:
        while len(ch) >= 2 and orientation(p, ch[-1], ch[-2]) < 0:
            ch.pop() # Remove a point from the upper hull
        ch.append(p) # Add a point to the upper hull
    return ch
 
def lowerHull(P):
  P2 = [(-p[0], -p[1]) for p in P] # Turn 180 degrees
  ch = upperHull(P2)
  return [(-p[0], -p[1]) for p in ch] # Undo the turn of 180 degrees
 
def convexHull(P):
    upper = upperHull(P)
    print("upper = ", upper)
    lower = lowerHull(P)
    print("lower = ", lower)
    return upper[0:-1] + lower[0:-1] # Concatenate upper and lower hulls
 
P = [(0,3),(4,7),(2,9),(1,5),(3,2),(10,8),(4,2),(15,8),(3,5)]
print("P = ", P)
ch = convexHull(P)
print("ch = ", ch)