Origami Warp
平面上有 N 条互不相同的直线。第 i 条直线经过两个不同的点 (ai,bi) 和 (ci,di)。
特别地,第一条直线为 x 轴,输入端点固定为 (0,0),(1,0);第二条直线为 y 轴,输入端点固定为 (0,0),(0,1)。
Alice 位于平面上。她可以进行任意次(包括零次)如下操作:
选择给定的一条直线,将自己移动到当前位置关于这条直线的对称点。
定义点 P 从点 S 可达,当且仅当:
对于任意实数 ε>0,都存在一个点 R,使得 Alice 能从 S 经过有限次操作到达 R,且 R 与 P 的欧几里得距离不超过 ε。
这里要求的是可以任意接近目标;所需操作次数可以随 ε 改变,不要求某一次有限操作恰好到达目标。给出的直线是无限长直线,操作过程中的位置不受输入坐标范围限制。
回答 Q 个询问。第 i 个询问给出整数 Xi,Yi,Zi,Wi:判断 (Zi,Wi) 是否从 (Xi,Yi) 可达。
共有 T 组测试,分别求解。
输入格式
第一行一个整数 T。接下来依次给出每组测试:
- 第一行一个整数 N。
- 接下来 N 行,每行四个整数 ai,bi,ci,di,描述第 i 条直线。
- 接下来一行一个整数 Q。
- 接下来 Q 行,每行四个整数 Xi,Yi,Zi,Wi,描述一个询问。
输出格式
按测试顺序,对每个询问输出一行:若目标可达,输出 Yes;否则输出 No。字母大小写任意,例如 YES、yEs 也合法。
数据范围
所有输入量都是整数。
- 1≤T≤100。
- 对每组测试,2≤N≤2000,1≤Q≤2000。
- −108≤ai,bi,ci,di≤108。
- (ai,bi)=(ci,di)。
- (a1,b1,c1,d1)=(0,0,1,0)。
- (a2,b2,c2,d2)=(0,0,0,1)。
- 给定的所有直线在几何上互不相同。
- −108≤Xi,Yi,Zi,Wi≤108。
没有额外的 ∑N 或 ∑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).
第四个询问的起终点相同,不进行操作即可。
第二组的第一个询问中,依次选择第一、第三条直线,可以移动到
$$(2,1)\longrightarrow(2,-1)\longrightarrow
\left(-\frac65,\frac{27}5\right).$$
最后一个点与目标 (−1,5) 的距离为 1/5。这给出了所有 ε≥1/5 时的一种方案;实际上,对任意更小的 ε>0 也存在合适的有限操作序列,所以这个询问的答案为 Yes。