No.2696 Sign Creation
タグ : / 解いたユーザー数 62
作問者 :
timi
/ テスター :
KowerKoint2010
hibit_at
mo124121
Dunsparce
Problem Statement
In this problem, a "constellation" is defined as $2$ or more "stars" connected by lines.
Chimi-kun loves gazing at the night sky. The night sky can be regarded as a rectangular grid of size $H × W$.
The $X$-axis points downward and the $Y$-axis points rightward; the $X$ coordinate is an integer between $1$ and $H$, inclusive, and the $Y$ coordinate is an integer between $1$ and $W$, inclusive.
Currently, $N$ stars can be observed in the night sky, and the coordinates of the $i$-th star are $(X_i,Y_i)$.
A star that is already part of a constellation may also be connected by a line to another star. (Added after the contest)
Now, the mischievous creator, Lord kys, has brought $1$ new star into being at coordinates where there was previously no star.
Find the minimum and maximum possible number of constellations that Chimi-kun can observe.
Note that the Manhattan distance between coordinates $(X_i,Y_i)$ and $(X_j,Y_j)$ is expressed as $|X_i-X_j|+|Y_i-Y_j|$.
Also, letting $(P,Q)$ be the coordinates of the newly born star, we have $1≤P≤H$ , $1≤Q≤W$, and both $P$ and $Q$ are integers.
Constraints
・All inputs are integers.・$1 \le H,W \le 100000=10^5$
・$H \times W \le 100000=10^5$
・$0 \le N \le H \times W-1 $
・$1≤D≤5$
・$1≤X_i≤H$
・$1≤Y_i≤W$
・At most $1$ star exists at any $1$ coordinate. That is, "if $i \neq j $, then $(X_i,Y_i) \neq (X_j,Y_j)$".
Input
$H\ W\ N\ D$ $X_1$ $Y_1$ $X_2$ $Y_2$ $︙$ $︙$ $X_N$ $Y_N$
Output
Print the minimum and the maximum, in this order, separated by a space.
Sample
Sample 1
Input
10 10 5 2 1 4 2 3 3 3 6 3 6 2
Output
1 2
Currently, the stars at $(1,4) , (2,3) , (3,3)$ form constellation $1$, and the stars at $(6,3) , (6,2)$ form constellation $2$. (Left figure)
For example, when a new star is born at $(4,3)$, constellation $1$, the new star, and constellation $2$ are connected by lines, and $1$ large constellation is observed. (Right figure)
Also, when a new star is born at $(8,1)$, the number of stars increases but the number of constellations does not, and the number of observed constellations remains $2$.
The minimum is $1$ and the maximum is $2$, so print
1 2.
Sample 2
Input
10 10 2 2 3 3 6 3
Output
0 1
Sample 3
Input
1 5 4 4 1 1 1 2 1 3 1 4
Output
1 1
Even Lord kys sometimes cannot change the number of constellations.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。