17166번 - Voronoi Diagram Again 서브태스크다국어

In the 2-dimensional Cartesian coordinate system, we define the Voronoi Diagram of a non-empty set of points $S$, as a diagram that divides the plane by the criteria ``which point in the set $S$ is closest in this location?". More precisely, the Voronoi diagram of a given non-empty point set $\{P_1, P_2, \cdots, P_n\}$ is a collection of \textbf{regions}: A point $K$ is included in region $i$ if and only if $d(P_i, K) \le d(P_j, K)$ holds for all $1 \le j \le n$. 

While the usual Voronoi Diagram uses Euclidean distance, we use Manhattan distance in this problem. $d(X, Y)$ denotes the \textbf{Manhattan} distance between point $X$ and $Y$. Manhattan distance between two points is the sum of the absolute differences of their $X$, $Y$ coordinates. Thus, the Manhattan distance between two points $(X_1, Y_1)$, $(X_2, Y_2)$ can be written as $|X_2 - X_1| + |Y_2 - Y_1|$.

For example, in the picture above, every location over the plane is colored by the closest point with such location. The points which belongs to a single region is colored by a light color indicating a region, and the points which belongs to more than one region forms lines and points colored black.

The region is unbounded if for any real number $R$, there exists point $P$ in the region such that $d(O, P) > R$ where $O$ is the origin. You have to find the number of unbounded regions in the Voronoi Diagram.

In the first line, the number of points consisting Voronoi diagram $N$ is given.

In the $i$-th line of next $N$ lines, two integers $x_i,\ y_i$ indicating $x$ and $y$ coordinate of $P_i$ are given. These are the points in the Voronoi diagram. 

Print a single integer, denoting 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.

This subtask has additional constraints:

• $N \le 2\,000$
• $-100 \le x_i,\ y_i \le 100$ ($1 \le i \le N$)

This subtask has an additional constraint:

• $N \le 2\,000$

This subtask has no additional constraints.

In example 2, overlapping region is indicated as subtractive mixing of two or more colors. All points with $(x \ge 5 \wedge  y \le 1) \vee (x \le 1 \wedge y \ge 5)$ is included in all five region, and colored as darkest.