data Direction = Left | Right | Straight deriving (Show, Eq)
type Coordinate = (Double, Double)

whichDirection :: Coordinate -> Coordinate -> Coordinate -> Direction
whichDirection (x2, y2) (x1, y1) (x3, y3)
  | crossProduct == 0 = Straight
  | crossProduct > 0  = Right
  | crossProduct < 0  = Left
  where crossProduct = (x2 - x1)*(y3 - y1) - (y2 - y1)*(x3 - x1)

listDirection :: [Coordinate] -> [Direction]
listDirection (a:b:c:xs) = (whichDirection a b c):(listDirection (b:c:xs))
listDirection _          = []

grahamScan :: [Coordinate] -> [Coordinate]
grahamScan ls@(a:b:c:xs) =
  let
    (pivot:rest) = sortBy (\ (x1, y1) (x2, y2) -> if y1 == y2 then compare x1 x2 else compare y1 y2) ls
    sortedRest   = sortBy (compare `on` (angle pivot)) rest ++ [pivot]
    listOfDirections = listDirection $ sortedRest ++ [pivot]
  in
    [pivot] ++ (makeHull sortedRest listOfDirections)
grahamScan _             = []

makeHull (a:b:c:xs) [] = [a]
makeHull (a:b:c:xs) (dir:ds) =
  if dir == Right
  then a:(makeHull (c:xs) ds)
  else a:(makeHull (b:c:xs) ds)
makeHull _ _         = []

angle (x1, y1) (x2, y2) = (dx / len, len) where
  dx = x1 - x2
  dy = y1 - y2
  len = sqrt (dx * dx + dy * dy)