Polyline Simplification

This problem gives us a list of connected points and asks us to remove points in order such that the the point removed at each step minimizes the area of the triangle formed between the removed point and the two surrounding points.

With a smaller input, we could just evaluate each triangle each time, but with 200k, it's clear the solution must be linearish.

The optimization required is pretty straightforward, and becomes obvious when we ask ourselves "what repeat work are we doing"?

Were we to do the n^2 solution, and recompute all triangles at each step, we'd notice that the only triangles which change are the ones spanned by the points immediately surrounding the point we removed. So we only need to recompute those two triangles.

One should realize from an implementation standpoint, in order to not have to walk the triangles again, we have to keep them in a treeset sorted by area. When we remove a triangle, we have to remove the now "invalid" triangles which might still be in the treeset before inserting the new ones.

One other challenge is how to find our "next" points after we've removed a bunch. We can't just use an array, since deleting is O(n), and we can't just walk the array to find the next "undeleted" point, since that is also O(n). It's clear we need to effectively maintain a linked list. When a point is removed, you look up your own current previous point, and point it to your own "next" point, and vice versa.