#P18239. Origami Warp

Origami Warp

Origami Warp

平面上有 NN 条互不相同的直线。第 ii 条直线经过两个不同的点 (ai,bi)(a_i,b_i) 和 (ci,di)(c_i,d_i)。

特别地,第一条直线为 xx 轴,输入端点固定为 (0,0),(1,0)(0,0),(1,0);第二条直线为 yy 轴,输入端点固定为 (0,0),(0,1)(0,0),(0,1)。

Alice 位于平面上。她可以进行任意次(包括零次)如下操作:

选择给定的一条直线,将自己移动到当前位置关于这条直线的对称点。

定义点 PP 从点 SS 可达,当且仅当:

对于任意实数 ε>0\varepsilon>0,都存在一个点 RR,使得 Alice 能从 SS 经过有限次操作到达 RR,且 RR 与 PP 的欧几里得距离不超过 ε\varepsilon。

这里要求的是可以任意接近目标;所需操作次数可以随 ε\varepsilon 改变,不要求某一次有限操作恰好到达目标。给出的直线是无限长直线,操作过程中的位置不受输入坐标范围限制。

回答 QQ 个询问。第 ii 个询问给出整数 Xi,Yi,Zi,WiX_i,Y_i,Z_i,W_i:判断 (Zi,Wi)(Z_i,W_i) 是否从 (Xi,Yi)(X_i,Y_i) 可达。

共有 TT 组测试,分别求解。

输入格式

第一行一个整数 TT。接下来依次给出每组测试:

  • 第一行一个整数 NN。
  • 接下来 NN 行,每行四个整数 ai,bi,ci,dia_i,b_i,c_i,d_i,描述第 ii 条直线。
  • 接下来一行一个整数 QQ。
  • 接下来 QQ 行,每行四个整数 Xi,Yi,Zi,WiX_i,Y_i,Z_i,W_i,描述一个询问。

输出格式

按测试顺序,对每个询问输出一行:若目标可达,输出 Yes;否则输出 No。字母大小写任意,例如 YES、yEs 也合法。

数据范围

所有输入量都是整数。

  • 1≤T≤1001\le T\le100。
  • 对每组测试,2≤N≤20002\le N\le2000,1≤Q≤20001\le Q\le2000。
  • −108≤ai,bi,ci,di≤108-10^8\le a_i,b_i,c_i,d_i\le10^8。
  • (ai,bi)≠(ci,di)(a_i,b_i)\ne(c_i,d_i)。
  • (a1,b1,c1,d1)=(0,0,1,0)(a_1,b_1,c_1,d_1)=(0,0,1,0)。
  • (a2,b2,c2,d2)=(0,0,0,1)(a_2,b_2,c_2,d_2)=(0,0,0,1)。
  • 给定的所有直线在几何上互不相同。
  • −108≤Xi,Yi,Zi,Wi≤108-10^8\le X_i,Y_i,Z_i,W_i\le10^8。

没有额外的 ∑N\sum N 或 ∑Q\sum Q 限制。

样例

输入

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

输出

Yes
Yes
No
Yes
Yes
Yes

样例说明

第一组的第一个询问中,依次选择第二、第三条直线,可以按如下方式移动:

(1,0)⟶(−1,0)⟶(2,3).(1,0)\longrightarrow(-1,0)\longrightarrow(2,3).

第四个询问的起终点相同,不进行操作即可。

第二组的第一个询问中,依次选择第一、第三条直线,可以移动到

$$(2,1)\longrightarrow(2,-1)\longrightarrow \left(-\frac65,\frac{27}5\right).$$

最后一个点与目标 (−1,5)(-1,5) 的距离为 1/51/\sqrt5。这给出了所有 ε≥1/5\varepsilon\ge1/\sqrt5 时的一种方案;实际上,对任意更小的 ε>0\varepsilon>0 也存在合适的有限操作序列,所以这个询问的答案为 Yes。