Several months ago I've seen a comment on Codeforces which explained a method of finding a tangent from a point to a polygon. This problem is rather hard and if you try the first implementation which comes to your mind, it probably will not work. That comment explained a tricky binary search where you should store not two endpoints of a segment, but three, and which was easy to implement.
However, now I cannot neither recall the idea nor find the comment itself. Could anyone help me with either?
Check this link : tangent to polygon.
Thanks, but that's not what I need. This is exactly an implementation which first comes to mind :) And there are some pitfalls you may encounter while implementing it. I'm searching for a simpler way.
The concept is that you take projection of all points of polygon on a vertical line(by joining point on polygon and the point from where you want to find tangent the point of intersection of vertical line and above line is the projection) after that you can take the projected point with maximum and minimum values of projected y and connect with given point to get tangents.
vertical line must lie between polygon and point
Edit : you could optimize it by using ternary search and computing the projection when required