Another nice application of orientation is to check whether a point \(p\) lies inside a convex polygon.

A **convex polygon** is a simple polygon (with no self intersections) such that any line segment between two points inside of the polygon lies completely inside of it.

The point will be inside a convex polygon if and only if it lies on the same side of the support line of each of the segments. That is, either it lies on the left of every line or it lines on the right of every line.

But we already know how to check whether a point lies on the right of left of a line defined by two points \(A\) and \(B\). For each polygon segment \(\overline{AB}\) we simply need to compute \(orient(A, B, P) = \vec{AB} \times \vec{AP}\) and check that they all have the same sign (which indicates the side).

Note that the solution is not to whether the point lies to the **right** of each line but to check whether the point lies on **the same side** of each line. In the above example it will indeed be always on the right by this is because the polygon is oriented in a clockwise fashion. If it had been oriented in a counter-clockwise fashion, the point would have been on the left of each line as show in the following figure.

If the polygon vertices are \(p_1, p_2, \ldots, p_n\) then we need to check that

### Information

Deadline | No deadline |

Submission limit | No limitation |