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

  • 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