CF391D1 Supercollider

本题包含两个子问题：解决子问题 D1 可获得 3 分，解决子问题 D2 可获得 16 分。 Manao 是负责规划新型超级对撞机的首席建筑师。他需要确定一块土地，以便建造尽可能大的超级对撞机。他正在建造的超级对撞机要求粒子以相同速度进行四向正交碰撞，因此对撞机将由四个加速腔组成，形状类似加号（即 +）。四个加速腔的长度必须相同，并且必须与地球磁场对齐（平行或正交），以最大限度地减少干扰。 加速腔需要铺设在长而平坦的土地上，以控制成本。因此，Manao 已经委托进行地形研究，确定了所有可用于建造加速腔、且与地球磁场平行或正交的最大长度土地段。为了建造最大的超级对撞机，Manao 必须在这些候选土地段中找出最大的对称加号形状。也就是说，他必须找到两段土地，使它们形成一个轴对齐的加号形状，并且从加号中心到四臂中最短一臂末端的距离最大。注意，对撞机不必使用土地段的全部长度（参见提示中的示例）。

输入的第一行包含两个用空格分隔的整数 $n$ 和 $m$，分别表示南北方向的土地段数和东西方向的土地段数。 接下来的 $n$ 行，每行描述一段南北方向的土地段。每段由三个用空格分隔的整数 $x_{i},y_{i},l_{i}$ 表示，代表从 $(x_{i},y_{i})$ 到 $(x_{i},y_{i}+l_{i})$ 的竖直线段。 随后是 $m$ 行，每行描述一段东西方向的土地段。每段由三个用空格分隔的整数 $x_{i},y_{i},l_{i}$ 表示，代表从 $(x_{i},y_{i})$ 到 $(x_{i}+l_{i},y_{i})$ 的水平线段。 所有 $x_{i}$ 和 $y_{i}$ 的取值范围为 $-100000000$ 到 $100000000$（包含端点）。所有 $l_{i}$ 的取值范围为 $1$ 到 $100000000$（包含端点）。任意两条水平线段不会接触或相交，任意两条竖直线段也不会接触或相交。 本题包含两个子问题。子问题的输入约束不同。正确提交子问题可获得相应分数。子问题描述如下： - 在子问题 D1（3 分）中，$n$ 和 $m$ 的取值范围为 $1$ 到 $1000$（包含端点）。 - 在子问题 D2（16 分）中，$n$ 和 $m$ 的取值范围为 $1$ 到 $50000$（包含端点）。

输出一行一个整数，表示可以用一条南北方向土地段和一条东西方向土地段建造的最大超级对撞机的尺寸。超级对撞机的尺寸定义为任一加速腔的长度。换句话说，超级对撞机的尺寸定义为两条线段交点到最近端点的距离。如果没有任何一对南北和东西方向的土地段相交，则无法建造超级对撞机，程序应输出最大尺寸为 $0$。

请参考以下示例。有一条竖直线段，从 $(4, 0)$ 到 $(4, 9)$，以及两条水平线段：从 $(1, 1)$ 到 $(9, 1)$ 和从 $(1, 2)$ 到 $(8, 2)$。这些线段中能形成的最大加号形状是由唯一的竖直线段和第二条水平线段组成，中心在 $(4, 2)$。 程序应输出 $2$，因为距离中心点 $(4, 2)$ 最近的端点是 $(4, 0)$，距离为 $2$。对撞机将由从 $(2, 2)$ 到 $(6, 2)$ 和从 $(4, 0)$ 到 $(4, 4)$ 的线段组成。 由 ChatGPT 4.1 翻译