Wednesday, November 14, 2012

Project Euler 184

Here it is.

Between fellowship applications and my senior design course, I've been quite busy, but I managed to sneak this one in.

Other people managed to find some insanely fast solutions, but I am fairly fond of my O(n^2) (n is number of points) solution - it is elegant and only relies on simple arguments.

It involves scoring "arms" or "angles" formed by triplets of points, depending on where origin is relative to the arms.  E.g. is it on one of the arms?  Directly behind?  Would the origin be "scooped up" by the arms if we were to extend them arbitrarily?

Hint -- the argument is fairly similar to the solution for Div 1 C of this Codeforces competition.  ;)

Happy solving.
-S