{"problem":{"name":"Origami Warp","description":{"content":"You are given $N$ lines on the $xy$\\-plane. The $i$\\-th line $(1 \\le i \\le N)$ passes through two distinct points $(a_i, b_i)$ and $(c_i, d_i)$. Specifically, $(a_1, b_1, c_1, d_1) = (0, 0, 1, 0)$ and","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"ttpc2024_1_f"},"statements":[{"statement_type":"Markdown","content":"You are given $N$ lines on the $xy$\\-plane. The $i$\\-th line $(1 \\le i \\le N)$ passes through two distinct points $(a_i, b_i)$ and $(c_i, d_i)$. Specifically, $(a_1, b_1, c_1, d_1) = (0, 0, 1, 0)$ and $(a_2, b_2, c_2, d_2) = (0, 0, 0, 1)$. That is, the first line represents the $x$\\-axis, and the second line represents the $y$\\-axis.\nAlice is on the $xy$\\-plane. She can perform the following operation any number of times (including zero):\n\n> Choose one of the $N$ given lines. Alice moves to the position symmetric to her current position with respect to the chosen line.\n\nAdditionally, we define that point $P$ is **reachable** from point $S$ if the following condition is satisfied:\n\n> For any real number $\\varepsilon > 0$, there exists a point $Q$ such that the Euclidean distance between $Q$ and $P$ is at most $\\varepsilon$, and Alice can move from $S$ to $Q$ in a finite number of operations.\n\nAnswer $Q$ queries. For the $i$\\-th query $(1 \\le i \\le Q)$, you are given integers $X_i, Y_i, Z_i, W_i$. Output `Yes` if $(Z_i, W_i)$ is reachable from $(X_i, Y_i)$. Otherwise, output `No`.\nSolve the problem for $T$ test cases.\n\n## Constraints\n\n*   All input values are integers.\n*   $1 \\le T \\le 100$\n*   For each test case:\n    *   $2 \\le N \\le 2000$\n    *   $1 \\le Q \\le 2000$\n    *   $-10^8 \\le a_i, b_i, c_i, d_i \\le 10^8 \\ (1 \\le i \\le N)$\n    *   $(a_i, b_i) \\neq (c_i, d_i)$\n    *   $(a_1, b_1, c_1, d_1) = (0, 0, 1, 0)$\n    *   $(a_2, b_2, c_2, d_2) = (0, 0, 0, 1)$\n    *   All given lines are distinct.\n    *   $-10^8 \\le X_i, Y_i, Z_i, W_i \\le 10^8 \\ (1 \\le i \\le Q)$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$\\text{case}_1$\n$\\text{case}_2$\n$\\vdots$\n$\\text{case}_T$\n\nHere, $\\text{case}_i$ represents the $i$\\-th test case. Each test case is given in the following format:\n\n$N$\n$a_1$ $b_1$ $c_1$ $d_1$\n$a_2$ $b_2$ $c_2$ $d_2$\n$\\vdots$\n$a_N$ $b_N$ $c_N$ $d_N$\n$Q$\n$X_1$ $Y_1$ $Z_1$ $W_1$\n$X_2$ $Y_2$ $Z_2$ $W_2$\n$\\vdots$\n$X_Q$ $Y_Q$ $Z_Q$ $W_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"ttpc2024_1_f","tags":[],"sample_group":[["2\n3\n0 0 1 0\n0 0 0 1\n0 2 2 0\n4\n1 0 2 3\n1 -2 -1 2\n1 1 -1 0\n3 3 3 3\n3\n0 0 1 0\n0 0 0 1\n-2 1 2 3\n2\n2 1 -1 5\n-1 -1 3 3","Yes\nYes\nNo\nYes\nYes\nYes\n\nLet us explain the first test case. For the first query, Alice can use the second and third lines in sequence to move $(1, 0) \\to (-1, 0) \\to (2, 3)$. Thus, $(2, 3)$ is reachable from $(1, 0)$. Note that for the fourth query, if $(X_i, Y_i) = (Z_i, W_i)$, the destination is always reachable.\nNow let us explain the second test case. For the first query, Alice can use the first and third lines in sequence to move $(2, 1) \\to (2, -1) \\to \\left(-\\frac{6}{5}, \\frac{27}{5}\\right)$. The distance between $(-1, 5)$ and $\\left(-\\frac{6}{5}, \\frac{27}{5}\\right)$ is $\\frac{1}{\\sqrt{5}}$. This means that for $\\varepsilon \\ge \\frac{1}{\\sqrt{5}}$, Alice can find a point $Q$ that satisfies the \"reachable\" condition. Moreover, for any $\\varepsilon > 0$, Alice can find such a point $Q$. As a result, $(2, 1)$ is reachable from $(-1, 5)$."]],"created_at":"2026-03-03 11:01:14"}}