405985: GYM102202 C Voronoi Diagram Again

Figure: Voronoi Diagram of size 4.

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 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 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.

• $$$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.

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

4
0 0
-4 0
3 4
4 -2

4

5
1 1
2 2
3 3
4 4
5 5

5

9
-4 -4
-4 0
-4 4
0 -4
0 0
0 4
4 -4
4 0
4 4

8

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.