分数: 100 点
问题陈述
你被给予 N 行 xy- 平面。 i第行 (1 \le i \le N) 穿过两个不同的点 (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)。也就是说,第一行代表 x- 轴,第二行代表 y- 轴。
爱丽丝正在 xy- 平面。她可以执行以下操作任意次数(包括零次):
选择其中一项 N 给定行。 Alice 移动到与她当前位置相对于所选线对称的位置。
此外,我们定义了这一点 P is 可达 从点 S 如果满足以下条件:
对于任何实数 \varepsilon > 0,存在一个点 Q 这样之间的欧几里德距离 Q 和 P 最多是 \varepsilon,爱丽丝可以从 S to Q 在有限数量的操作中。
答案 Q 查询。
对于 i第一个查询 (1 \le i \le Q),给你整数 X_i, Y_i, Z_i, W_i。输出 Yes if (Z_i, W_i) 可以从 (X_i, Y_i)。否则,输出 No.
解决以下问题 T 测试用例。
约束
- 所有输入值均为整数。
- 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) \neq (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)
输入
输入由标准输入按以下格式给出:
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 \le i \le Q) 应包含以下问题的答案 i-第一个查询。
法官不区分大小写 Yes 和 No.
示例输入 1
2 3 0 0 1 0 0 0 0 1 0 2 2 0 4 1 0 2 3 1 -2 -1 2 1 1 -1 0 3 3 3 3 3 0 0 1 0 0 0 0 1 -2 1 2 3 2 2 1 -1 5 -1 -1 3 3
示例输出 1
Yes Yes No Yes Yes Yes
让我们解释一下第一个测试用例。对于第一个查询,Alice 可以依次使用第二行和第三行来移动 (1, 0) \to (-1, 0) \to (2, 3)。因此, (2, 3) 可以从 (1, 0)。请注意,对于第四个查询,如果 (X_i, Y_i) = (Z_i, W_i),目的地始终可达。
现在让我们解释第二个测试用例。对于第一个查询,Alice 可以依次使用第一行和第三行来移动 (2, 1) \to (2, -1) \to \left(-\frac{6}{5}, \frac{27}{5}\right)。之间的距离 (-1, 5) 和 \left(-\frac{6}{5}, \frac{27}{5}\right) is \frac{1}{\sqrt{5}}。这意味着对于 \varepsilon \ge \frac{1}{\sqrt{5}}, Alice 可以找到一个点 Q 满足“可达”条件。此外,对于任何 \varepsilon > 0,Alice可以找到这样一个点 Q。结果, (2, 1) 可以从 (-1, 5).