問題一覧 > 通常問題

No.2696 Sign Creation

レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 80
作問者 : timitimi / テスター : KowerKoint2010KowerKoint2010 hibit_athibit_at mo124121mo124121 DunsparceDunsparce
1 ProblemId : 10606 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-23 10:25:29

問題文

この問題では、$2$ つ以上の「星」が線で結ばれたものを「星座」と定義します。
　
ちみ君は夜空を眺めることが大好きです。夜空は $H × W$ の、長方形の形をしたグリッドとして捉えることができます。
$X$ 軸は下向き、$Y$ 軸は右向きで、$X$ 座標は $1$ 以上 $H$ 以下、$Y$ 座標は $1$ 以上 $W$ 以下の整数です。
現在、夜空には $N$ 個の星が観測でき、$i$番目の星の座標は $(X_i,Y_i)$ と表せます。

星同士のマンハッタン距離が $D$ 以下であるとき、ちみ君は星と星を線で結び、$1$ つの「星座」と認識します。
すでに星座となっている星が、別の星と線で結ばれることもありえます。(コンテスト後追記)

ここで、いたずら好きの創造主 kys 様が、今まで星がなかった座標に $1$ つの星を新しく誕生させました。
ちみ君が観測できる星座はいくつになるのか、ありえる最小値と最大値をそれぞれ求めてください。

なお、座標 $(X_i,Y_i)$ と $(X_j,Y_j)$ とのマンハッタン距離は、$|X_i-X_j|+|Y_i-Y_j|$ と表されます。
また、新しく誕生する星の座標を $(P,Q)$ としたとき、$1≤P≤H$ , $1≤Q≤W$ であり、$P$ と $Q$ は共に整数であるとします。

制約

・入力はすべて整数
・$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$
・$1$ つの座標に星は高々 $1$ つしか存在しない。すなわち、「 $i \neq j $ であれば、 $(X_i,Y_i) \neq (X_j,Y_j)$ 」である。

入力

$H\ W\ N\ D$ 
$X_1$ $Y_1$
$X_2$ $Y_2$
$︙$  $︙$ 
$X_N$ $Y_N$

出力

最小値、最大値の順番に、空白区切りで出力してください。

サンプル

サンプル1
入力
10 10 5 2
1 4
2 3
3 3
6 3
6 2
出力
1 2
　　　　　　
現在 $(1,4) , (2,3) , (3,3)$ の星が星座$1$、$(6,3) , (6,2)$ の星が 星座$2$ を成しています。(左図)
たとえば新たな星が $(4,3)$ に誕生したとき、星座$1$ ・新たな星・星座$2$ が線で結ばれ、大きな星座 $1$つが観測されるようになります。（右図）
また、新たな星が $(8,1)$ に誕生したとき、星は増えますが星座が増えず、観測される星座は $2$つ のままです。
最小値が $1$ 、最大値が $2$ なので、1 2と出力してください。

サンプル2
入力
10 10 2 2
3 3
6 3
出力
0 1

サンプル3
入力
1 5 4 4
1 1
1 2 
1 3
1 4
出力
1 1

kys 様といえど、星座の数を変えられないこともあります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。