| Are the points vertexes of a convex N-gon? |
Complexity (1-100): 20
Cartesian coordinates of N points on a plane are given. Are these points vertexes of a convex N-gon? |
| Solution: | Show/hide explanation | solution.pas |
| Explanation |
Imagine
that we have attached a thread to the bottommost point and stretched it
to the right. Lets turn the thread counter-clockwise, keeping it
stretched. The thread will touch other points and turn around them. The
angle between the thread and the horizon will increase. Consider the
thread is turning around the point A k. We can know for certain which of the points it will touch next. It is such a point A k+1 which constitutes the minimal angle between the current thread position and the line A kA k+1.
Finally, we return to the bottommost point. If that happen and there are
points which the thread did not touch, then the answer is no (the
points cannot be the vertexes of a convex N-gon). See self-tests. |