AT_1_ttpc2024_1_f.Origami Warp

在 $xy$ 平面上，给定 $N$ 条直线。第 $i$ 条直线 $(1 \le i \le N)$ 通过两个不同的点 $(a_i, b_i)$ 和 $(c_i, d_i)$。特别地，$1$ 号直线和 $2$ 号直线分别表示 $x$ 轴和 $y$ 轴，即 $(a_1, b_1, c_1, d_1) = (0, 0, 1, 0)$ 和 $(a_2, b_2, c_2, d_2) = (0, 0, 0, 1)$。

Alice 站在 $xy$ 平面上的某个位置，她可以反复进行以下操作：

她可以选择任意一条直线，并移动到当前点关于该直线的对称位置。

对于点 $S$ 是否能“到达”点 $P$，我们这样定义：

对于任意实数 $\varepsilon > 0$，都存在一个点 $Q$，使得 $Q$ 与 $P$ 的欧几里得距离不超过 $\varepsilon$，并且 Alice 能从 $S$ 通过有限次操作移动到 $Q$。

现在，你需要回答 $Q$ 个查询。对于第 $i$ 个查询 $(1 \le i \le Q)$，给出整数 $X_i, Y_i, Z_i, W_i$，判断是否能从 $(X_i, Y_i)$ 到达 $(Z_i, W_i)$，如果可以，输出 Yes，否则输出 No。

需要解决 $T$ 组测试用例。

输入由以下形式给出：

T
case_1
case_2
...
case_T

其中，$\text{case}_i$ 代表第 $i$ 个测试用例。每个测试用例格式如下：

N
a_1 b_1 c_1 d_1
a_2 b_2 c_2 d_2
...
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
...
X_Q Y_Q Z_Q W_Q

对于每个测试用例，输出 $Q$ 行。每行输出相应查询的结果，即 Yes 或 No。注意，输出时不区分大小写。

• 所有输入均为整数。
• $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)$。

对于实例来说：

• 在第一个测试用例的第一个查询中，可以通过使用第 $2$ 条直线和第 $3$ 条直线，移动从 $(1, 0)$ 到达 $(-1, 0)$ 再到 $(2, 3)$，所以 $(1, 0)$ 可以归到 $(2, 3)$。
• 第四个查询说明，如果 $(X_i, Y_i) = (Z_i, W_i)$，则该点总是可以到达自己的。

在第二个测试用例中：

• 第一个查询可以使用第 $1$ 和第 $3$ 条直线，变换路径为 $(2, 1) \rightarrow (2, -1) \rightarrow \left(-\frac{6}{5}, \frac{27}{5}\right)$。由于 $(-1, 5)$ 和 $\left(-\frac{6}{5}, \frac{27}{5}\right)$ 的距离是 $\frac{1}{\sqrt{5}}$，对于任何 $\varepsilon \ge \frac{1}{\sqrt{5}}$，都可以视为到达。所以 $(2, 1)$ 能到达 $(-1, 5)$。

本翻译由 AI 自动生成