Voronoi Diagram Again

A Voronoi diagram of a non-empty point set $S$ divides the plane by the question of which point in $S$ is closest to a given location. More precisely, for a point set $\{P_1, P_2, \cdots, P_n\}$, a point $K$ belongs to region $i$ if and only if $d(P_i, K) \le d(P_j, K)$ holds for all $1 \le j \le n$. The usual Voronoi diagram uses Euclidean distance, but this problem uses Manhattan distance. $d(X, Y)$ is the Manhattan distance between $X$ and $Y$, which is the sum of the absolute differences of their $x$ and $y$ coordinates. So the Manhattan distance between $(X_1, Y_1)$ and $(X_2, Y_2)$ is $|X_2 - X_1| + |Y_2 - Y_1|$.

In the figure above, every location on the plane is colored by its closest point. Locations that belong to a single region have a light color, and locations that belong to more than one region form black lines and points.

A region is unbounded if, for any real number $R$, there is a point $P$ in the region with $d(O, P) > R$, where $O$ is the origin. Find the number of unbounded regions in the Voronoi diagram.

The first line contains $N$, the number of points in the Voronoi diagram. Each of the next $N$ lines contains two integers $x_i$ and $y_i$, the coordinates of point $P_i$.

Print a single integer, the number of unbounded regions in the Voronoi diagram.

• $1 \le N \le 250\,000$
• $-10^9 \le x_i,\ y_i \le 10^9$ ($1 \le i \le N$)
• All $N$ points are distinct.

In example 2, the overlapping area is shown as a subtractive mix of two or more colors. Every point with $(x \ge 5 \wedge y \le 1) \vee (x \le 1 \wedge y \ge 5)$ belongs to all five regions, so it is colored darkest.