Good day, Codeforces!
Given a polygon with N vertices, where the vertices(x[i], y[i]) are listed in counterclockwise order, you need to check if an angle is concave in the polygon. To better understand what is meant, refer to the provided illustrations:
By (ABC) I will mean the angle where B is the vertex of the angle, and A and C are the sides of the angle.
In that pic, (AFE) and (EDC) are concave angles.
Sorry for my bad English, any help will be appreciated.
Google Cross Product:
The thing about concavity is that if you go one way, by turning left, one time you might end up turning right. This is because in a convex polygon, all adjacent vertices vectors are traversed by angle while traversed in some order. Concave polygons do not respect this, the order of the adjacent vertices vectors have their angle spawned randomly across the unit circle. As such, to adjust from one adjacent vector to the next, you might have to rotate both clockwise and counter-clockwise (assuming you rotate only with <180 degrees). If you use both, then it means that it is not convex.
Thank you! Excuse me, but do you have code for that?
No. But check this page for more such details.