8622: Monotone Chain

A polygon $P$ is called monotone with respect to a straight line $L$, if every line orthogonal to $L$ intersects the boundary of $P$ at most twice. For many practical purposes, this definition may be extended to allow cases when some edges of $P$ are orthogonal to $L$.

A monotone polygon can be split into two monotone polygonal chains. A polygonal chain is a connected series of line segments, which can be specified by a sequence of points {A1,A2,…,An}\{A_1,A_2,\dots,A_n\}{A1,A2,…,An}. Similarly, a polygonal chain $C$ is called monotone with respect to a straight line $L$, if every line orthogonal to $L$ intersects $C$ at most once, or some line segments of $C$ are orthogonal to $L$.

In this problem, we denote a directed line La,bL_{\mathbf{a,b}}La,b by a point $\mathbf{a}$ and a direction vector $\mathbf{b}$ where La,b={a+λb∣λ∈R}L_{\mathbf{a,b}}=\{\mathbf{a}+\lambda\mathbf{b}|\lambda\in\mathbb{R}\}La,b={a+λb∣λ∈R}. We define a polygonal chain C={A1,A2,…,An}C=\{A_1,A_2,\dots,A_n\}C={A1,A2,…,An} to be monotone with respect to a directed line La,bL_{\mathbf{a,b}}La,b if the following condition is satisfied:

• For any 1≤i<j≤n1 \le i < j \le n1≤i<j≤n, (OAi−a)⋅b≤(OAj−a)⋅b(\mathbf{OA_i}-\mathbf{a})\cdot\mathbf{b}\le(\mathbf{OA_j}-\mathbf{a})\cdot\mathbf{b}(OAi−a)⋅b≤(OAj−a)⋅b.

Here, OAi\mathbf{OA_i}OAi means the coordinate of the point AiA_iAi, and "$\cdot$'' means the dot product of vectors.

Now given the $n$ points in a polygonal chain $C$, please determine whether there exists a directed line La,bL_{\mathbf{a,b}}La,b such that $C$ is monotone with respect to La,bL_{\mathbf{a,b}}La,b.

The first line contains an integer $n$ (1≤n≤1051 \le n \le 10^51≤n≤105), indicating the number of points in the polygonal chain.
Each of the next $n$ lines contains two integers x,yx,yx,y (−105≤x,y≤105-10^5 \le x,y \le 10^5−105≤x,y≤105), indicating the coordinates of the points in the polygonal chain. Please note that there may be identical points, even two adjacent points.

If there exists a directed line La,bL_{\mathbf{a,b}}La,b such that the polygonal chain is monotone with respect to La,bL_{\mathbf{a,b}}La,b, output $\text{YES}$ in the first line. Then output four integers x1,y1,x2,y2x_1,y_1,x_2,y_2x1,y1,x2,y2 (−109≤x1,y1,x2,y2≤109-10^9 \le x_1,y_1,x_2,y_2 \le 10^9−109≤x1,y1,x2,y2≤109, (x2,y2)≠(0,0)(x_2,y_2)\neq(0,0)(x2,y2)=(0,0)) in the second line, indicating that a=(x1,y1)\mathbf{a}=(x_1,y_1)a=(x1,y1) and b=(x2,y2)\mathbf{b}=(x_2,y_2)b=(x2,y2). If there are multiple answers, output any.
Otherwise, output $\text{NO}$ in a single line.

4
0 1
2 0
0 3
4 3

YES
0 -3 1 1