• + 0 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