#121. Solder

传统 1000 ms 256 MiB
标准 IO
文本比较 admin 标签

题目描述

一辆喷涂着修正集团广告的和谐号动车组列车呼啸驶来,打断了 aa 那极其中二的 YY。

走上列车,aa 才发觉他还要给集训队选拔出一道计算几何题。

“可是我并不会那些圆的面积并啊什么的啊。” aa 想着。

突然 aa 想到了他的电工电子实践初步课上焊的板子。因为内部的部分电路是断的,所以 aa 不得不用焊料把两个焊点强行焊接起来。

那如果我随意用焊料画几个线段呢?接下来随便选取几个点,问他们是否联通?

“emmmm,似乎是不错的题目。” aa 想着并把题出了出来。

现在,aa 来考你了。

输入格式

本题有多组测试数据,文件第一行为测试数据组数 T(1T10)T(1\leq T\leq 10)

对于每一组测试数据,第一行为两个整数 n, m(1n, m103)n,\ m(1\leq n,\ m\leq 10^3),分别表示随意画的线段个数和询问个数。

接下来 nn 行,每行四个整数 x1, y1, x2, y2x_1,\ y_1,\ x_2,\ y_2 表示 aa 从 (x1, y1)(x_1,\ y_1)(x2, y2)(x_2,\ y_2) 画了个线段。

再接下来 mm 行,每行四个整数 x1, y1, x2, y2x_1,\ y_1,\ x_2,\ y_2 表示询问从 (x1, y1)(x_1,\ y_1)(x2, y2)(x_2,\ y_2) 是否联通,即将直流电源正负极接到两个坐标后电源是否短路(忽略焊料的电阻)。

输入由整数、空格、回车组成,每个整数的绝对值均小于 10810^8

输出格式

对于每一个如果询问,如果电源短路输出YES,否则输出NO

样例

样例输入

1
3 7
1 3 3 5
1 5 6 2
5 7 7 4
2 4 6 2
1 3 6 2
1 3 6 1
0 0 0 0
0 0 1 1
5 7 7 4
5 7 2 4

样例输出

YES
YES
NO
YES
NO
YES
NO