No.678 2Dシューティングゲームの必殺ビーム

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 69
作問者 : horiesinitihoriesiniti / テスター : はむこはむこ

2 ProblemId : 1209 / 出題時の順位表

問題文

下から上へ向かう2D縦シューティングゲームの幅広ビームの当たり判定を実装します。 ゲームでは自機から母艦に要請して母艦から幅広ビームを発射してもらえます。 ビームの当たり判定を実装してください。

ビームの当たり判定や敵データは以下のルールに従う。

  • ビームの幅はビームの左端が$xLB$ピクセル目から右側の$xRB$ピクセル目までの範囲(画面の左端から右へ1ピクセルずつ数えたときのピクセル座標)。
  • ビームの高さは画面一番下はるか遠く(無限と考えても構わない)から画面一番上まで届きます。
  • ビームは縦横X軸Y軸にきっちりした四角形の範囲になります。
  • 必殺ビームですので当然自機には当たりません。
  • ビームは画面下から上に発射されたものと仮定し敵に当たるとその範囲のビームはストップし、その背後にいる敵には当たりません。
  • ビームは一ドットでも当たればあたりですが一ドットでもずれていればはずれと判定します。
  • 敵の当たり判定も縦横きっちりした四角形であり斜めの四角形ということはありません。

(言葉ではわかりにくいと思う。図入りでサンプルインプットを解説しているのでそれを参照すること)

入力

$N$ $xLB$ $xRB$
$XL_1$ $YU_1$ $XR_1$ $YD_1$
$\dots$
$XL_n$ $YU_n$ $XR_n$ $YD_n$

画面サイズは横幅1280ピクセル、縦幅1680ピクセルで固定であり、入力データは全て整数値であり敵の数を除きピクセル座標をさすと仮定してよい。
画面一番左上のドットが(1,1)で画面一番右下のドットが(1280,1680)である。
敵は必ず一部分か全体が画面に入っていると仮定してよい。
どの2敵を選んでも当たり判定のドット範囲が重なっているということはない。
敵の左と右、上と下が同じ座標の場合1*1ドットの敵と判定する。

$0 \le N \le 188$
$ 0 \le xLB < xRB \le 1280$
$-500 \le XL_i \le 1280$
$max(0,XL_i) \le XR_i \le 2000$
$-500 \le YU_i \le 1680$
$max(0,YU_i) \le YD_i \le 2180$

$N$は敵の数である。 $xLB$はビームの左端、$xRB$はビームの右端である。 続く$N$行にわたり敵$i$の当たり判定が与えられる。 敵$i$の当たり判定の左上が($XL_i$,$YU_i$)右下が($XR_i$,$YD_i$)で敵は斜めでない縦横に従った四角形である。

出力

$H_1$
$\dots$
$H_n$

出力$H_i$は敵$i$が必殺ビームに当たっているなら1でないなら0を一行ずつ出力すること。

最後に改行してください。

サンプル

サンプル1
入力
6 30 200
25 150 50 175
100 150 125 175
150 150 175 175
75 100 160 125
74 50 100 75
130 50 165 75
出力
1
1
1
1
1
0

水色の部分がビームの有効範囲である。 敵は赤色の四角である。 敵4の左x座標は75、敵5の左x座標は74である。 4が壁になってるように見えるが、敵5左X座標は74なのでビームに当たっている。 もし敵5の左x座標が75ならビームは一ドットの差で当たっていないことになる。 敵6は4と3が壁になってビームに当たっていない。

もう少し例を出す。 もし左座標が100で右座標が200の敵に左端が0右端が300のビームが当たれば。 ビームは0~99と201~300の二つに分かれる。

サンプル2
入力
6 30 190
-20 75 50 100
80 120 130 140
166 90 200 120
40 45 165 60
140 10 200 20
35 20 50 30
出力
1
1
1
1
0
0

敵1、2,3、4はあたっている。 敵3、4による絶妙なブロックで敵5はガードされている。 もし敵3、4が1ドットでもずれれば敵5にビームは当たる。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。