問題一覧 > 通常問題

No.2696 Sign Creation

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

問題文

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

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

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

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

制約

・入力はすべて整数
・1≤H,W≤100000=1051 \le H,W \le 100000=10^5
・H×W≤100000=105H \times W \le 100000=10^5
・0≤N≤H×W−10 \le N \le H \times W-1
・1≤D≤51≤D≤5
・1≤Xi≤H1≤X_i≤H
・1≤Yi≤W1≤Y_i≤W
・11 つの座標に星は高々 11 つしか存在しない。すなわち、「 i≠ji \neq j であれば、 (Xi,Yi)≠(Xj,Yj)(X_i,Y_i) \neq (X_j,Y_j) 」である。

入力

H W N DH\ W\ N\ D 
X1X_1 Y1Y_1
X2X_2 Y2Y_2
︙︙  ︙︙ 
XNX_N YNY_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,4) , (2,3) , (3,3) の星が星座11、(6,3),(6,2)(6,3) , (6,2) の星が 星座22 を成しています。(左図)
たとえば新たな星が (4,3)(4,3) に誕生したとき、星座11 ・新たな星・星座22 が線で結ばれ、大きな星座 11つが観測されるようになります。（右図）
また、新たな星が (8,1)(8,1) に誕生したとき、星は増えますが星座が増えず、観測される星座は 22つ のままです。
最小値が 11 、最大値が 22 なので、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もしくは右上の雲マークをクリックしてアカウントを作成してください。