RealWorldHaskell-3_12.hs

import Data.List

data Point = Point Int Int deriving Show
data Direction = DLeft
               | DRight
               | DStraight

findPointP :: [Point] -> [Point]
findPointP points = sortBy smallestYthenX points
    where smallestYthenX (Point x1 y1) (Point x2 y2)
              | y2 < y1 = GT
              | y2 > y1 = LT
              | otherwise = if x2 < x1
                            then GT
                            else LT
                       
increasingOrderOfAngle :: [Point] -> [Point]
increasingOrderOfAngle (pointP : points) = pointP : (sortBy increasingOrderOfAngle points)
    where increasingOrderOfAngle pointA pointB = if (angle pointP pointA) >= (angle pointP pointB)
                                                 then GT
                                                 else LT
          angle (Point x y) (Point x2 y2) = atan(fromIntegral(y2 - y)/fromIntegral(x2 - x))

direction :: Point -> Point -> Point -> Direction
direction (Point x1 y1) (Point x2 y2) (Point x3 y3)
    | cross == 0 = DStraight
    | cross > 0 = DLeft
    | cross < 0 = DRight
    where cross = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)
                  
isLeft :: Direction -> Bool
isLeft DLeft = True
isLeft _ = False

grahamScan :: [Point] -> Point -> Point -> [Point] -> [Point]
grahamScan acc in1 in2 (x:xs)
    | isLeft(direction in1 in2 x) = grahamScan (in2 : acc) in2 x xs
    | otherwise = grahamScan acc in1 in2 xs
grahamScan acc _ _ [] = reverse acc

findConvexHull points = pointP : pointB : grahamScan [] pointP pointB rest
    where pointP : pointB : rest = (increasingOrderOfAngle (findPointP points))

test = findConvexHull [Point 1 1, Point 9 9, Point 0 0, Point 0 9, Point 9 0, Point 3 3, Point 10 10]