Recognizing Convex Grid Graphs

You are given $N$ distinct lattice points $(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)$.

Construct an undirected graph $G$ whose vertices are the given points. Two distinct points $(x_i,y_i)$ and $(x_j,y_j)$ are connected by an edge if their Manhattan distance is $1$.

The Manhattan distance between $(x_i,y_i)$ and $(x_j,y_j)$ is

The graph $G$ is a convex grid graph if, for every pair of vertices $i,j$, their shortest-path distance in $G$ equals the Manhattan distance between the corresponding points. If two vertices are disconnected, their graph distance is defined to be infinity.

Determine whether the given graph is a convex grid graph.

The input is given from Standard Input in the following format:

$N$ $x_1\ y_1$ $x_2\ y_2$ $\vdots$ $x_N\ y_N$

Print YES if the given graph is a convex grid graph, and print NO otherwise.

Uppercase and lowercase letters are distinct.

• $1 \leq N \leq 500\,000$.
• $-10^9 \leq x_i,y_i \leq 10^9$ ($1 \leq i \leq N$).
• $(x_i,y_i) \neq (x_j,y_j)$ ($1 \leq i < j \leq N$).