P10190 [USACO24FEB] Target Practice II S

**注意：本题的时间限制为 2.5 秒，通常限制的 1.25 倍。** **注意：这个问题涉及到的整数可能需要使用 64 位整数型（例如，C/C++ 中的 `long long`）。**

巴黎哞运会即将来临，Farmer John 正在对他的奶牛队进行射箭训练！他在二维坐标平面上设置了以下练习。 有 $N$（$1\le N\le 4\cdot 10^4$）个四边与坐标轴平行的矩形箭靶和 $4N$ 头奶牛。每头牛都必须被分配一个不同的箭靶顶点。对于 $1\le i\le N$，在时刻 $i$： 1. 箭靶 $i$ 出现。 2. 分配其顶点的 $4$ 头奶牛向它们射箭。 3. 如果奶牛的箭在击中所分配的顶点之前穿过箭靶内部，或未命中，则奶牛们的练习失败。 4. 箭靶消失，为下一个箭靶腾出空间。 每头牛都位于 $y$ 轴（$x=0$）上，每个箭靶都是一个矩形，其中箭靶 $i$ 的左下顶点坐标为 $(X_1,y^{(i)}_1)$，右上顶点坐标为 $(x^{(i)}_2,y^{(i)}_2)$。所有坐标满足 $1\le X_1

输入的第一行包含 $T$（$1\le T\le 10$），为测试用例的数量。每个测试用例的描述如下： 每个测试用例的第一行包含两个整数 $N$ 和 $X_1$，分别为箭靶的数量以及所有箭靶的左端的 $x$ 坐标。 以下 $N$ 行，第 $i$ 行包含三个整数 $y^{(i)}_1$，$y^{(i)}_2$ 和 $x^{(i)}_2$，分别为第 $i$ 个箭靶的下端 $y$ 坐标，上端 $y$ 坐标和右端 $x$ 坐标。 最后一行包含 $4N$ 个整数 $s_1,s_2,\ldots,s_{4N}$，其中 $s_i$ 表示奶牛 $i$ 的射箭轨迹的斜率。

输出最远奶牛之间的最小可能距离，或如果奶牛总是练习失败时输出 $−1$。

### 样例解释 对于测试用例 $1$，一个最佳分配方案是分别为奶牛 $1-8$ 分配以下目标顶点： $$(6,1),(6,3),(3,4),(3,6),(1,4),(1,3),(1,6),(1,1)$$ 这得出了奶牛 $1-8$ 的 $y$ 坐标如下： $$−5,9,−2,12,1,6,2,5$$ 这给出了最小距离 $12−(−5)=17$。 第二个测试用例的答案是不可能的原因之一是，如果箭不穿过箭靶 $1$ 的内部，不可能射中 $(6,3)$ 处的顶点（箭靶 $1$ 的右上顶点）。 ### 测试点性质 - 测试点 $2$：对于所有的 $1\le i\le 4N$，$|S_i|$ 均相同。 - 测试点 $3-9$：所有测试用例的 $N$ 之和不超过 $1000$。 - 测试点 $10-15$：没有额外限制。