시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 (추가 시간 없음) | 1024 MB | 197 | 46 | 45 | 29.032% |
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.
This subtask has additional constraints:
This subtask has an additional constraint:
This subtask has no additional constraints.
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.
University > KAIST > 2019 KAIST RUN Spring Contest C번