AT_ttpc2024_1_f Origami Warp

$ xy $ 平面上に $ N $ 本の直線が与えられます。 $ i $ 本目 $ (1 \le i \le N) $ の直線は異なる $ 2 $ 点 $ (a_i,b_i),(c_i,d_i) $ を通る直線です。ただし、 $ (a_1,b_1,c_1,d_1)=(0,0,1,0) $ 、 $ (a_2,b_2,c_2,d_2)=(0,0,0,1) $ です。すなわち、 $ 1 $ 本目の直線は $ x $ 軸を表しており、 $ 2 $ 本目の直線は $ y $ 軸を表しています。 Alice が $ xy $ 平面上にいます。Alice は、以下の操作を $ 0 $ 回以上好きな回数行うことができます。 > 与えられた $ N $ 本の直線のうち $ 1 $ つを選ぶ。Alice は、選んだ直線について現在位置と線対称な位置に移動する。 また、点 $ S $ から点 $ P $ に**到達可能である**ということを、次のように定義します。 > 任意の実数 $ \varepsilon >0 $ について、 $ P $ とのユークリッド距離が $ \varepsilon $ 以下であるような点 $ Q $ が存在して、Alice が $ S $ から $ Q $ に有限回の操作で移動できる。 $ Q $ 個のクエリに答えてください。 $ i $ 番目 $ (1

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ ここで、 $ \text{case}_i $ は $ i $ 番目のテストケースを表す。各テストケースは以下の形式で与えられる。 > $ N $ $ a_1 $ $ b_1 $ $ c_1 $ $ d_1 $ $ a_2 $ $ b_2 $ $ c_2 $ $ d_2 $ $ \vdots $ $ a_N $ $ b_N $ $ c_N $ $ d_N $ $ Q $ $ X_1 $ $ Y_1 $ $ Z_1 $ $ W_1 $ $ X_2 $ $ Y_2 $ $ Z_2 $ $ W_2 $ $ \vdots $ $ X_Q $ $ Y_Q $ $ Z_Q $ $ W_Q $

各テストケースに対して、 $ Q $ 行出力せよ。そのうち $ i $ 行目 $ (1

### Sample Explanation 1 最初のテストケースについて述べます。 $ 1 $ つ目のクエリについて、 $ 2 $ 本目、 $ 3 $ 本目の直線を順に使うことで、 $ (1,0) \rightarrow (-1,0) \rightarrow (2,3) $ と移動することができるので、 $ (1,0) $ から $ (2,3) $ は到達可能です。 $ 4 $ つ目のクエリについて、 $ (X_i,Y_i)=(Z_i,W_i) $ であるときは常に到達可能なことに注意してください。 $ 2 $ 番目のテストケースについて述べます。 $ 1 $ つ目のクエリについて、 $ 1 $ 本目、 $ 3 $ 本目と順に使うと、 $ (2,1) \rightarrow (2,-1) \rightarrow (-\frac{6}{5},\frac{27}{5}) $ と移動することができます。 $ (-1,5) $ と $ (-\frac{6}{5},\frac{27}{5}) $ の距離は $ \frac{1}{\sqrt{5}} $ なので、 $ \varepsilon \ge \frac{1}{\sqrt{5}} $ に対しては、問題文中の到達可能の条件を満たすような $ Q $ として $ (-\frac{6}{5},\frac{27}{5}) $ をとることができます。同様に、任意の $ \varepsilon > 0 $ に対しても $ Q $ をとることができるため、 $ (2,1) $ から $ (-1,5) $ は到達可能です。 ### Constraints - 入力はすべて整数 - $ 1 \le T \le 100 $ - 各テストケースについて: - $ 2 \le N \le 2000 $ - $ 1 \le Q \le 2000 $ - $ -10^8 \le a_i,b_i,c_i,d_i \le 10^8 \ (1 \le i \le N) $ - $ (a_i,b_i) \ne (c_i,d_i) $ - $ (a_1,b_1,c_1,d_1)=(0,0,1,0) $ - $ (a_2,b_2,c_2,d_2)=(0,0,0,1) $ - 与えられる直線はすべて異なる - $ -10^8 \le X_i,Y_i,Z_i,W_i \le 10^8 \ (1 \le i \le Q) $