reimai 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"
rexim You are so awesome! Thank you very much! It really helped me. :)
Stanley_Goldman I was able to do it very quickly with https://www.desmos.com/
joel_chelliah 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.
abhiranjan Congrats :) It's good to know you learnt something new.
oleg_patraschku same here ... I submitted the graham scan firstly then I had problem with the 4th test ... so I tried the QuickHull and indeed it doesn't return the points in order so you will calculate a false perimeter , unless you do smth. more :)
penkovsky 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/
Cheers,
codeonwort 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
alexey_filippov Did the Jarvis march (the gift wrapping algorithm) — works like charm!
zgrogan Fun! If you're doing Haskell and having trouble, do Real World Haskell's Ch03 exercises. They'll get you most of the way there.
phun601 Akl-Toussaint octagonal heuristics filters out nearly all (90%+) the points from each of the test case.
asoares Does anyone could share the convex hull points for test #4? My perimeter is slightly different from expected. My points:
[[44 3] [26 3] [17 6] [17 971] [44 995] [956 995] [974 971] [977 958] [977 6]]My perimeter:3868.9581Expected:3874.1vladimir_i_tikh1 I encounted similar issue when trying to implement Graham scan algorithm. It appeared that I did not handle collinear case properly. In your case, your points do not create hull for test #4, as there are several points outside polygon, e.g. point [116 3] is outside segment [[44 3] - [26 3]] though all the three points belongs to a line.
Elmex90s [deleted]
MarcoMaar I used andrew's monotone chain algorithm in F#. Was a nice example.
logrus I have a problem with the test case #4, (other ones are computed correctly) and I can't find a bug in my code. My results are: Hull: List((329,3), (44,3), (17,6), (17,971), (26,992), (44,995), (956,995), (974,971), (977,958), (977,6), (26,3)) Perimeter: 4479.6 Can someone post his #4 hull for comparison? Thanks!
Sort 15 Discussions, By:
Please Login in order to post a comment