We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Functional Programming
  3. Recursion
  4. Convex Hull
  5. Discussions

Convex Hull

Sort by

recency

|

27 Discussions

|

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

  • parthamazumder02
     + 1 comment

    Why c or c++ is not added for submission language?

  • demo_kioussis
     + 0 comments

    Man, Im in the middle of learning haskell. I come from a background of C++ / C# and I just felt so clunky writing this code. The other beginner problems made me feel pretty good in hask until here

  • alexcornejo
     + 0 comments

    Is not possible to tackle this problem using Java? :(

  • iamhere2
     + 0 comments

    Really cool challenge! I had had to remember parts of linear algebra and analytic geometry, which I knew fairly well at university, but, of course, completely forgot.

    I've decided to solve the task firstly without looking up to the well-known algorithms, and I finally did it! My first straightforward solution was O(N^2), so, to pass all the test cases, I had rescue to a simple optimization trick. First of all, I build a simple octagon, based on points with min/max x/y coordinates. That octagon lies completely in the convex hull, so I could filter out a lot of "internal" points, using this simple approximation. After that, straightforward (bruteforce) algorithm worked quite well and fast for all test cases. Later I have found that I reinvented the "Akl–Toussaint heuristic" on my own! :)

    Of course, after that, I've read about well-known algorithms, and implemented QuickHull. The most interesting part was to make it return ordered points, for simple perimeter calculation.

    The core of my final solution with F# (without I/O):

    let vprod ((xa1, ya1), (xa2, ya2)) ((xb1, yb1), (xb2, yb2)) =
    (xa2 - xa1) * (yb2 - yb1) - (ya2 - ya1) * (xb2 - xb1)

let pdir (p1, p2) p = vprod (p1, p2) (p1, p) |> sign
let atRightOf v p = pdir v p < 0
let heightScore (p1, p2) p = vprod (p1, p2) (p1, p) |> abs

let orderedQuickHull ps = Seq.toList (seq {
    let rec rightHull basement ps = seq {
        let atRight = ps |> List.filter (atRightOf basement)
        yield! if atRight.IsEmpty then Seq.empty
               else
                    let farthest = atRight |> List.maxBy (heightScore basement)
                    seq { yield! rightHull (farthest, snd basement) atRight;
                          yield farthest;
                          yield! rightHull (fst basement, farthest) atRight }
        }
    let pMin = List.min ps
    let pMax = List.max ps
    yield pMin
    yield! rightHull (pMax, pMin) ps
    yield pMax
    yield! rightHull (pMin, pMax) ps
})

let len ((x1, y1), (x2, y2)) =
    let dx = x1 - x2
    let dy = y1 - y2
    dx * dx + dy * dy |> float |> sqrt

let orderedPerimeter ps =
    ps @ [List.head ps] |> List.pairwise |> List.sumBy len