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.
Convex Hull
Convex Hull
Sort by
recency
|
26 Discussions
|
Please Login in order to post a comment
Why c or c++ is not added for submission language?
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
Is not possible to tackle this problem using Java? :(
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):
Here's my homebrewed Clojure solution:
It selects an "extreme" point, i.e. one that's assuredly on the perimeter, then for each point it finds the next point that's the smallest angular distance from the previous point.
This solution is a bit brute force insofar as for each step it considers all other points as possibilities for an angle check. It succeeds on 4 out of 5 of the test data sets but times out on the last one.