Sort 24 Discussions, By:
Please Login in order to post a comment
If you're having trouble with the last one - gnuplotting the thing really helps:
$ tail -n +2 test_case | gnuplot -p -e "plot '-' using 1:2 with points"
Just managed to solve this after spending what feels like an insane amount of time. Definitely the hardest one I've tried so far, but also really rewarding to finally get it right! :D
I used the Quickhull algorithm which was fairly easy to implement. The tricky part was getting all points in the correct order before calculating the perimeter. It helped me a lot to draw it out on paper first.
Really nice challenge. It appears, there are quite a lot of tricky parts: e.g. finding the minimal point with respect to both y and x coordinates, filtering the points that form equivalent angles between the starting point and O-X axis, etc. Finally, one should be careful when ordering the points.
Visualizing my intermediate hulls was of great help to finally solve the problem.
And this article is definitely worth reading http://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/
I passed the test with my own algorithm, not googling any previous one :D :D :D it's awesome!
After that I googled and found mine was just a cumbersome version of Graham scan. lol
Did the Jarvis march (the gift wrapping algorithm) — works like charm!