問題一覧 > 通常問題

No.2696 Sign Creation

レベル : / AI推定難易度 : 1400 / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 62
作問者 : timi / テスター : KowerKoint2010 hibit_at mo124121 Dunsparce
お気に入りにしたユーザー ProblemId : 10606 / 自分の提出
問題文最終更新日: 2026-04-30 15:42:54
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 423 (Asakatsu Presents 3) (順位表) の他の問題:

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

When the Manhattan distance between stars is at most $D$, Chimi-kun connects those stars with a line and recognizes them as $1$ "constellation".
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もしくは右上の雲マークをクリックしてアカウントを作成してください。