C - Fracture Ray
問題文
BobはAliceを怒らせました。Aliceは破壊光線でBobを消滅させようとしています。Bobが回避することができるか答えてください。
より具体的に述べましょう。Aliceは時刻 $K + 0.5$ に $N$ 発の破壊光線をすべて同時に発射します。 $i$ 本目の破壊光線はBobからユークリッド距離が $10^{100}$ 離れた地点から発射されます。破壊光線の情報は $1$ つの格子点 $(p_i, q_i)$ と $3$ つの整数 $u_i, v_i, r_i$ で与えられ、これは破壊光線が格子点 $(p_i, q_i)$ を通り、方向ベクトルが $(u_i, v_i)$ である直線から距離 $r_i$ 以内の点の集合であることを表しています。
はじめに、整数 $N, K, H, W, Q$ および $N$ 本の破壊光線の情報が与えられます。
その後、次の形式の質問が $Q$ 個与えられます。すべての質問について答えてください。
- $i$ 個目の質問では、Bobが時刻 $0$ において $2$ 次元平面上の格子点 $(X_i, Y_i)$ にいることを表す正整数 $X_i, Y_i$ が与えられる。Bobは $1$ 秒でその時点でいる格子点から $4$ 方向に隣接する格子点（より厳密には、ユークリッド距離が $1$ である格子点） $(x, y)$ のうち、 $0 \le x \le W, 0 \le y \le H$ を満たす格子点に瞬間的に移動することができる（ただし、今いる格子点から動かないことも可能）。Bobが適切に移動することですべての破壊光線を回避することが可能か？ただし、格子点がちょうど破壊光線の境界線上にある場合も、破壊光線に当たっていると見做す。
制約
Final (65点)
- $1 \le N \le 1000$
- $0 \le K \le \min(100, H + W)$
- $0 \le H, W \le 10^5$
- $1 \le Q \le 100$
- $0 \le p_i \le W$
- $0 \le q_i \le H$
- $u_i$ と $v_i$ は次の条件をすべて満たす。
- $-1000 \le u_i, v_i\le 1000$
- $|u_i| + |v_i| \ne 0$
- $u_iv_i \ne 0$ ならば $|u_i|$ と $|v_i|$ は互いに素
- $u_i = 0$ ならば $|v_i| = 1$
- $v_i = 0$ ならば $|u_i| = 1$
- $1 \le r_i \le 2 \times \max(H, W)$
- $0 \le X_i \le W$
- $0 \le Y_i \le H$
- 入力はすべて整数である。
Hard (45点)
- Finalの制約に以下の制約を追加
- $0 \le K \le \min(10, H + W)$
Normal (20点)
- Finalの制約に以下の制約を追加
- $0 \le K \le \min(10, H + W)$
- $|u_i| + |v_i| = 1$
Easy (60点)
- Finalの制約に以下の制約を追加
- $K = H + W$
- $H + W \le 10$
- $|u_i| + |v_i| = 1$
Beginning (10点)
- Finalの制約に以下の制約を追加
- $N = 1$
- $K = W$
- $H = 0$
- $0 \le W \le 10$
- $u_i = 0$
- $v_i = 1$
入力
$N\ \ K\ \ H\ \ W\ \ Q$
$p_1\ \ q_1\ \ u_1\ \ v_1\ \ r_1$
$p_2\ \ q_2\ \ u_2\ \ v_2\ \ r_2$
$\ \vdots$
$p_N\ \ q_N\ \ u_N\ \ v_N\ \ r_N$
$X_1\ \ Y_1$
$X_2\ \ Y_2$
$\ \vdots$
$X_Q\ \ Y_Q$
出力
$Q$ 行出力してください。
$i$ 行目には、 $i$ 個目の質問において、Bobがすべての破壊光線を回避することが可能なら Yes 、そうでなければ No を出力し、最後に改行してください。
1 10 0 10 1
4 0 0 1 5
0 0
Yes
Bobは点 $(10, 0)$ に移動することで破壊光線を回避することができます。
入力例1はBeginning, Easy, Normal, Hard, Finalの制約を満たします。
1 2 1 1 1
0 1 -1 0 1
0 1
No
どこに動いても破壊光線を回避することができません。
入力例2はEasy, Normal, Hard, Finalの制約を満たします。
5 10 100 100 10
72 12 859 494 2
58 41 128 553 17
97 20 77 449 17
2 57 -204 -709 39
38 60 92 85 16
76 38
8 16
61 45
77 6
89 86
31 88
48 13
93 75
38 93
25 80
Yes
No
No
Yes
Yes
No
No
Yes
No
No
入力例3はHard, Finalの制約を満たします。