← 返回题目列表

AtCoder · ttpc2024_1_f

F. 折纸变形

中文机器翻译题面 查看原题

分数: 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).