题目描述

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.

4
10 -5
2 -5
-7 6
-7 -8

Yes

12
17 1
19 3
12 10
19 17
17 19
10 12
3 19
1 17
8 10
1 3
3 1
10 8

No