Target Practice II

题目描述

注意：本题时间限制为 2.5s，是默认时间限制的 1.25 倍。 注意：本题涉及的整数范围较大，可能需要使用 64 位整数类型（例如 C/C++ 中的 "long long"）。

巴黎 Moolympics 即将到来，FJ 正在训练他的奶牛队练习射箭！他在二维坐标平面上设计了如下训练。

有 $N (1 \leq N \leq 4 \cdot 10^4)$ 个与坐标轴平行的矩形靶子，以及 $4N$ 头奶牛。每头奶牛必须被分配到一个不同的靶子顶点。

在时刻 $i$（$1 \leq i \leq N$）： 靶子 $i$ 出现。 分配到其四个顶点的 $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$）描述。

为了能仔细观察奶牛们的技术，FJ 希望最小化最远两头奶牛之间的距离。如果 FJ 可以最优地将每头奶牛分配到某个靶子顶点并把它们放置在 $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

标签: USACO|2024|Silver

来源

USACO|2024|Silver