import Data.List

newtype Stack a = Stack [a] deriving Show

newStack :: Stack a
newStack = Stack []

push :: a -> Stack a -> Stack a
push x (Stack xs) = Stack (x : xs)

top :: Stack a -> Maybe a
top (Stack []) = Nothing
top (Stack (x:_)) = Just x

pop :: Stack a -> Stack a
pop (Stack []      ) = Stack []
pop (Stack (_ : xs)) = Stack xs

stackLength :: Stack a -> Int
stackLength (Stack xs) = length xs

nextToTop :: Stack a -> Maybe a
nextToTop (Stack []) = Nothing
nextToTop (Stack (_:[])) = Nothing
nextToTop (Stack (_:y:_)) = Just y

asList :: Stack a -> [a]
asList (Stack xs) = xs

data Point = Cartesian Float Float
    deriving (Show, Ord, Eq)

ccw :: Point -> Point -> Point -> Float

ccw (Cartesian ax ay) (Cartesian bx by) (Cartesian cx cy) =
    (bx - ax) * (cy - ay) - (cx - ax) * (by - ay)

getLowerLeftMostPoint :: [Point] -> Maybe Point
getLowerLeftMostPoint [] = Nothing
getLowerLeftMostPoint points = Just (minimumBy sortFun points)

sortFun :: Point -> Point -> Ordering
sortFun (Cartesian x1 y1) (Cartesian x2 y2) = case compare y1 y2 of
    EQ       -> compare x1 x2
    anything -> anything

-- Euclidean distance
dist :: Point -> Point -> Float
dist (Cartesian x1 y1) (Cartesian x2 y2) = sqrt (f x1 x2 + f y1 y2)
    where f a b = (a - b) ** 2



testData :: [Point]
testData =
    [ (Cartesian 0.3215348546593775 0.03629583077160248)
    , (Cartesian 0.02402358131857918 (-0.2356728797179394))
    , (Cartesian 0.04590851212470659 (-0.4156409924995536))
    , (Cartesian 0.3218384001607433 0.1379850698988746)
    , (Cartesian 0.11506479756447 (-0.1059521474930943))
    , (Cartesian 0.2622539999543261 (-0.29702873322836))
    , (Cartesian (-0.161920957418085) (-0.4055339716426413))
    , (Cartesian 0.1905378631228002 0.3698601009043493)
    , (Cartesian 0.2387090918968516 (-0.01629827079949742))
    , (Cartesian 0.07495888748668034 (-0.1659825110491202))
    , (Cartesian 0.3319341836794598 (-0.1821814101954749))
    , (Cartesian 0.07703635755650362 (-0.2499430638271785))
    , (Cartesian 0.2069242999022122 (-0.2232970760420869))
    , (Cartesian 0.04604079532068295 (-0.1923573186549892))
    , (Cartesian 0.05054295812784038 0.4754929463150845)
    , (Cartesian (-0.3900589168910486) 0.2797829520700341)
    , (Cartesian 0.3120693385713448 (-0.0506329867529059))
    , (Cartesian 0.01138812723698857 0.4002504701728471)
    , (Cartesian 0.009645149586391732 0.1060251100976254)
    , (Cartesian (-0.03597933197019559) 0.2953639456959105)
    , (Cartesian 0.1818290866742182 0.001454397571696298)
    , (Cartesian 0.444056063372694 0.2502497166863175)
    , (Cartesian (-0.05301752458607545) (-0.06553921621808712))
    , (Cartesian 0.4823896228171788 (-0.4776170002088109))
    , (Cartesian (-0.3089226845734964) (-0.06356112199235814))
    , (Cartesian (-0.271780741188471) 0.1810810595574612)
    , (Cartesian 0.4293626522918815 0.2980897964891882)
    , (Cartesian (-0.004796652127799228) 0.382663812844701)
    , (Cartesian 0.430695573269106 (-0.2995073500084759))
    , (Cartesian 0.1799668387323309 (-0.2973467472915973))
    , (Cartesian 0.4932166845474547 0.4928094162538735)
    , (Cartesian (-0.3521487911717489) 0.4352656197131292)
    , (Cartesian (-0.4907368011686362) 0.1865826865533206)
    , (Cartesian (-0.1047924716070224) (-0.247073392148198))
    , (Cartesian 0.4374961861758457 (-0.001606279519951237))
    , (Cartesian 0.003256207800708899 (-0.2729194320486108))
    , (Cartesian 0.04310378203457577 0.4452604050238248)
    , (Cartesian 0.4916198379282093 (-0.345391701297268))
    , (Cartesian 0.001675087028811806 0.1531837672490476)
    , (Cartesian (-0.4404289572876217) (-0.2894855991839297))
    ]

test :: [Point]
test = graham testData

graham :: [Point] -> [Point]
graham points = asList (foldl  performScan newStack sortedPoints)
    where
        Just p0 = getLowerLeftMostPoint points
        f p1 p2 = let orientation = ccw p0 p1 p2 in
            case compare orientation 0 of
                EQ -> compare (dist p0 p1**2) (dist p0 p2**2)
                GT -> LT
                LT -> GT
        sortedPoints = sortBy f points

-- scan :: Stack Point -> [Point] -> Stack Point
-- scan st [] = st
-- scan st (x : xs) = scan (performScan st x) xs

performScan :: Stack Point -> Point -> Stack Point
performScan st p0 = if (stackLength st > 1) && (ccw second first p0) < 0
    then performScan (pop st) p0
    else push p0 st
    where
        Just first = top st
        Just second = nextToTop st

main :: IO()
main = print $ test