P15736 [JAG 2024 Summer Camp #2] Half Plane Painting

You have a 2D plane that is initially entirely white. You can perform the following operation any number of times: - Choose a line and the half-plane bounded by this line. Then, perform one of the following actions: - Paint the half-plane (excluding the boundary) black. - Paint the half-plane and the boundary white. You are given the polygon $P$ with $N$ vertices, which is not necessarily convex. The vertices of $P$ are given in counterclockwise order as $(x_1, y_1)$, $(x_2, y_2)$, $\ldots$, $(x_N, y_N)$, and the $i$-th edge of $P$ connects vertex $(x_i, y_i)$ to vertex $(x_{(i \mod N) + 1}, y_{(i \mod N) + 1})$. Determine whether it is possible to use the aforementioned operations to paint only the interior of polygon $P$ black, leaving everything else white.

The input is given in the following format: $$ \begin{aligned} &N \\ &x_1 \ y_1 \\ &x_2 \ y_2 \\ &\vdots \\ &x_N \ y_N \end{aligned} $$ - $3 \leq N \leq 4,000$ - $-10^7 \leq x_i, y_i \leq 10^7 \quad (1 \leq i \leq N)$ - $(x_i, y_i) \neq (x_j, y_j) \quad (i \neq j)$ - The vertices of polygon $P$ are given in counterclockwise order. - The edges of polygon $P$ do not share any points other than the vertices. - Each internal angle of polygon $P$ is not $180$ degrees. - All input values are integers.

If it is possible to achieve the desired state with the operations, output **Yes**; otherwise, output **No**.