Monotone Chain

题号：NC239623
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

See Problem N for PDF statements.

In computational geometry, polygon triangulation is the decomposition of a polygonal area into a set of triangles. Over time, a number of algorithms have been proposed to triangulate a polygon. One of the special cases is the triangulation of the monotone polygon. It is proved that a monotone polygon can be triangulated in linear time.

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 $\{A_1,A_2,\dots,A_n\}$ . 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 $L_{\mathbf{a,b}}$ by a point $\mathbf{a}$ and a direction vector $\mathbf{b}$ where $L_{\mathbf{a,b}}=\{\mathbf{a}+\lambda\mathbf{b}|\lambda\in\mathbb{R}\}$ . We define a polygonal chain $C=\{A_1,A_2,\dots,A_n\}$ to be monotone with respect to a directed line $L_{\mathbf{a,b}}$ if the following condition is satisfied:

For any $1 \le i < j \le n$ , $(\mathbf{OA_i}-\mathbf{a})\cdot\mathbf{b}\le(\mathbf{OA_j}-\mathbf{a})\cdot\mathbf{b}$ .

Here, $\mathbf{OA_i}$ means the coordinate of the point $A_i$ , 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 $L_{\mathbf{a,b}}$ such that $C$ is monotone with respect to $L_{\mathbf{a,b}}$ .

输入描述:

The first line contains an integer  (), indicating the number of points in the polygonal chain.

Each of the next  lines contains two integers  (), 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  such that the polygonal chain is monotone with respect to , output  in the first line. Then output four integers  (, ) in the second line, indicating that  and . If there are multiple answers, output any.

Otherwise, output  in a single line.

示例1

输入

复制

输出

复制

YES
0 -3 1 1

说明

A possible solution for the first sample:

示例2

输入

复制

输出

复制

NO