Problem 1. Target Practice II

USACO 2024 February Contest, Silver

注意：本题的时间限制为 2.5 秒，通常限制的 1.25 倍。

注意：这个问题涉及到的整数可能需要使用 64 位整数型（例如，C/C++ 中的 "long long"）。

巴黎哞运会即将来临，Farmer John 正在对他的奶牛队进行射箭训练！他在二维坐标平面上设置了以下练习。

有 $N$（$1 \leq N \leq 4 \cdot 10^4$）个四边与坐标轴平行的矩形箭靶和 $4N$ 头奶牛。每头牛都必须被分配一个不同的箭靶顶点。对于 $1 \leq i \leq N$，在时刻 $i$：

1. 箭靶 $i$ 出现。
2. 分配其顶点的 $4$ 头奶牛向它们射箭。
3. 如果奶牛的箭在击中所分配的顶点之前穿过箭靶内部，或未命中，则奶牛们的练习失败。
4. 箭靶消失，为下一个箭靶腾出空间。

每头牛都位于 $y$ 轴（$x = 0$）上，每个箭靶都是一个矩形，其中箭靶 $i$ 的左下顶点坐标为 $(X_1, y_1^{(i)})$，右上顶点坐标为 $(x_2^{(i)}, y_2^{(i)})$。所有坐标满足 $1 \leq X_1 < x_2^{(i)}\leq 10^9$ 以及 $1 \leq y_1^{(i)} < y_2^{(i)} \leq 10^9$（注意：$X_1$ 对于每个箭靶都是相同的）。

此外，每头奶牛都有一个正在钻研的「瞄准」角度。因此她们在射箭时会转向特定的角度。考虑到她们的箭从她们的位置沿直线射向指定的顶点，奶牛 $i$ 的箭的轨迹可以用轨迹的斜率 $s_i$（$0 < |s_i| < 10^9$）来表示。

为了能够仔细检查奶牛们的技术，Farmer John 希望尽量缩短最远的奶牛之间的距离。如果 Farmer John 以最佳方式给每头奶牛分配箭靶顶点并将她们放置在 $y$ 轴上，你能否帮助他求出最远奶牛之间的最小距离是多少，或者奶牛是否总是会练习失败？

每个测试点包含 $T$（$1 \leq T \leq 10$）个独立的测试用例。输入保证所有测试用例的 $N$ 之和不超过 $4\cdot 10^4$。

输入格式（从终端 / 标准输入读入）：

输入的第一行包含 $T$（$1 \leq T \leq 10$），为测试用例的数量。每个测试用例的描述如下：

每个测试用例的第一行包含两个整数 $N$ 和 $X_1$，分别为箭靶的数量以及所有箭靶的左端的 $x$ 坐标。

以下 $N$ 行，第 $i$ 行包含三个整数 $y_1^{(i)}$，$y_2^{(i)}$ 和 $x_2^{(i)}$，分别为第 $i$ 个箭靶的下端 $y$ 坐标，上端 $y$ 坐标和右端 $x$ 坐标。

最后一行包含 $4N$ 个整数 $s_1, s_2, \dots, s_{4N}$，其中 $s_i$ 表示奶牛 $i$ 的射箭轨迹的斜率。

输出格式（输出至终端 / 标准输出）：

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

输入样例：

3
2 1
1 3 6
4 6 3
1 -1 2 -2 3 -3 4 -4
2 1
1 3 6
4 6 3
1 1 2 2 3 3 4 4
2 1
1 3 3
4 6 3
1 -1 2 -2 3 -3 4 -4

输出样例：

17
-1
11

对于测试用例 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 \leq i \leq 4N$，$|S_i|$ 均相同。测试点 3-9：所有测试用例的 $N$ 之和不超过 $1000$。测试点 10-15：没有额外限制。

供题：Suhas Nagar