You are viewing a single comment's thread. Return to all comments →
My Haskell Solution
import Data.List -- Data structure to represent points type Point = (Double, Double) -- Cross product of three points crossProduct :: Point -> Point -> Point -> Double crossProduct (x1, y1) (x2, y2) (x3, y3) = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1) -- Calculate the distance between two points distance :: Point -> Point -> Double distance (x1, y1) (x2, y2) = sqrt ((x2 - x1) ^ 2 + (y2 - y1) ^ 2) -- Find the convex hull of a list of points convexHull :: [Point] -> [Point] convexHull points = let sortedPoints = sort points lowerHull = buildHull sortedPoints upperHull = buildHull (reverse sortedPoints) in lowerHull ++ tail upperHull -- Build the convex hull from a sorted list of points buildHull :: [Point] -> [Point] buildHull = foldl addPoint [] where addPoint [] p = [p] addPoint [h] p = [p, h] addPoint (h1:h2:t) p | crossProduct h2 h1 p > 0 = addPoint (h2:t) p | otherwise = p : h1 : h2 : t -- Calculate the perimeter of the convex hull convexHullPerimeter :: [Point] -> Double convexHullPerimeter points = sum $ zipWith distance hull (tail hull ++ [head hull]) where hull = convexHull points -- Parse input and calculate convex hull perimeter main :: IO () main = do n <- readLn :: IO Int points <- mapM (\_ -> fmap ((\[x, y] -> (x, y)) . map read . words) getLine) [1..n] let result = convexHullPerimeter points putStrLn $ show result
Seems like cookies are disabled on this browser, please enable them to open this website
Convex Hull
You are viewing a single comment's thread. Return to all comments →
My Haskell Solution