Q5: ペイントソフト
(paizaランク S 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
※この問題は、2021年1月に開催されたP共通テスト（バンタンテックフォードアカデミー中高プログラミング共通テスト）で出題された問題です。
ソフトウェア会社で働いている太郎さんは、自社の 100 色ペイントソフトの塗りつぶし機能についての業務を任されました。
具体的な業務の内容は以下の通りです。
1. y 軸方向の長さが H, x 軸方向の長さが W である、上のような座標系の H × W のキャンバスを用意します。
はじめに、キャンバスは白色 (カラーコード 1番) で塗られており、 4 個の長方形が描かれています。
各長方形の 4 つの頂点の組は次の通りです。
・(0,0), (0,y_1), (x_1,y_1), (x_1,0) ＜図中赤色＞
・(0,H), (x_2,H), (x_2,y_2), (0,y_2) ＜図中青色＞
・(W,H), (W,y_3), (x_3,y_3), (x_3,H) ＜図中緑色＞
・(W,0), (x_4,0), (x_4,y_4), (W,y_4) ＜図中黄色＞
2. N 回塗りつぶしの操作をおこないます。
この操作では、キャンパスの端・長方形の辺で区切られている区画のうち、クリックした点と同じ区画を、選択したカラーコードの色で塗りつぶします。
i 回目の塗りつぶしでは、カラーコード C_i を選択した状態で点 (px_i, py_i) をクリックします。
既に色が塗られている区画を塗りつぶした場合、新しい色で上書きされることに注意してください。
3. 以下の形式の質問が Q 回与えられるので、その全てに回答してください。
「座標(qx_i, qy_i) の色はカラーコード何番ですか」
- 入力される値
-
N Q H W
x_1 y_1
x_2 y_2
x_3 y_3
x_4 y_4
C_1 px_1 py_1
...
C_N px_N py_N
qx_1 qy_1
...
qx_Q qy_Q
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
・Q 行出力してください。
・Q 行のうち i 行目では、点 (qx_i, qy_i) に塗られている色のカラーコードを出力してください。
塗りつぶしがおこなわれていない点であっても、白のカラーコード1を出力することに注意してください。
- 条件
-
・入力は全て整数
・1 ≦ N ≦ 1,000
・1 ≦ Q ≦ 1,000
・2 ≦ H ≦ 100,000
・2 ≦ W ≦ 100,000
・0 < x_i < W(1 ≦ i ≦ 4)
・0 < y_i < H(1 ≦ i ≦ 4)
・1 ≦ C_i ≦ 100 (1 ≦ i ≦ N)
・0 < px_i < W(1 ≦ i ≦ N)
・0 < py_i < H(1 ≦ i ≦ N)
・(px_i, py_i) が線上（長方形の辺上・キャンパスの縁上）の点でないことが保証されている。
・0 < qx_i < W(1 ≦ i ≦ Q)
・0 < qy_i < H(1 ≦ i ≦ Q)
・(qx_i, qy_i) が線上（長方形の辺上・キャンパスの縁上）の点でないことが保証されている。
- 入力例1
-
10 10 100 100
70 50
30 80
50 40
20 90
2 10 30
3 60 45
4 35 95
5 10 60
6 25 85
7 70 95
8 10 85
9 80 10
10 35 20
11 15 30
1 1
1 51
7 99
31 81
90 10
95 95
35 95
25 20
40 51
51 45
- 出力例1
-
11
5
8
1
9
7
4
10
1
3
