CF391D1.Supercollider

This problem consists of two subproblems: for solving subproblem D1 you will receive 3 points, and for solving subproblem D2 you will receive 16 points.

Manao is the chief architect involved in planning a new supercollider. He has to identify a plot of land where the largest possible supercollider can be built. The supercollider he is building requires four-way orthogonal collisions of particles traveling at the same speed, so it will consist of four accelerating chambers and be shaped like a plus sign (i.e., +). Each of the four accelerating chambers must be the same length and must be aligned with the Earth's magnetic field (parallel or orthogonal) to minimize interference.

The accelerating chambers need to be laid down across long flat stretches of land to keep costs under control. Thus, Manao has already commissioned a topographical study that has identified all possible maximal length tracts of land available for building accelerating chambers that are either parallel or orthogonal to the Earth's magnetic field. To build the largest possible supercollider, Manao must identify the largest symmetric plus shape from among these candidate tracts. That is, he must find the two tracts of land that form an axis-aligned plus shape with the largest distance from the center of the plus to the tip of the shortest of the four arms of the plus. Note that the collider need not use the entire length of the tracts identified (see the example in the notes).

本题包含两个子问题：解决子问题 D1 可获得 3 分，解决子问题 D2 可获得 16 分。

马瑙（Manao）是负责规划一座新型超级对撞机的首席建筑师。他需要选定一块土地，以建造尽可能大的超级对撞机。该超级对撞机要求粒子以相同速度沿正交方向（即上下左右四个方向）发生碰撞，因此它由四个加速腔组成，整体呈“加号”形（即 + 形）。这四个加速腔长度必须完全相等，且均需与地球磁场方向平行或垂直排列，以最小化干扰。

为控制建设成本，加速腔必须铺设在长而平坦的土地上。因此，马瑙已委托开展了一项地形勘测，识别出所有可用于建造加速腔的、长度最大的地块；这些地块的方向均与地球磁场平行或垂直。为建造尽可能大的超级对撞机，马瑙必须从这些候选地块中找出面积最大的、对称的“加号”形结构。换言之，他必须找出两条地块，使得它们构成一个轴对齐的“加号”形，并使该“加号”的中心到其四条臂中最短一臂末端的距离最大化。注意：对撞机无需使用所识别地块的全部长度（参见注释中的示例）。

The first line of the input will contain two single-space-separated integers n, the number of north-south tracts and m, the number of west-east tracts.

Each of the n lines following the first describes a north-south tract. Each such tract is described by three single-space-separated integers x__i, y__i, l__i representing the vertical line segment from (x__i, y__i) to (x__i, y__i + l__i).

Similarly, after the n lines describing north-south tracts follow m similar lines describing the west-east tracts. Each such tract is described by three single-space-separated integers x__i, y__i, l__i representing the horizontal line segment from (x__i, y__i) to (x__i + l__i, y__i).

All x__i and y__i are between -100000000 and 100000000, inclusive. All l__i are between 1 and 100000000, inclusive. No pair of horizontal segments will touch or intersect, and no pair of vertical segments will touch or intersect.

The problem consists of two subproblems. The subproblems have different constraints on the input. You will get some score for the correct submission of the subproblem. The description of the subproblems follows.

• In subproblem D1 (3 points), n and m will be between 1 and 1000, inclusive.
• In subproblem D2 (16 points), n and m will be between 1 and 50000, inclusive.

输入的第一行包含两个以单个空格分隔的整数 $n$（南北向地块的数量）和 $m$（东西向地块的数量）。

接下来的 $n$ 行每行描述一条南北向地块。每条南北向地块由三个以单个空格分隔的整数 $x_i,\,y_i,\,l_i$ 描述，表示从点 $(x_i,\,y_i)$ 到点 $(x_i,\,y_i + l_i)$ 的垂直线段。

类似地，在描述完 $n$ 条南北向地块之后，接下来的 $m$ 行分别描述 $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]$ 范围内（含端点）。

Print one line containing a single integer, the size of the largest supercollider that can be built on one north-south tract and one west-east tract. The size of the supercollider is defined to be the length of one of the four accelerating chambers. In other words, the size of the resulting supercollider is defined to be the distance from the intersection of the two line segments to the closest endpoint of either of the two segments. If no pair of north-south and west-east tracts intersects, it is not possible to build a supercollider and the program should report a maximum size of zero.

输出一行，包含一个整数，表示可在一条南北向轨道和一条东西向轨道上建造的最大型超级对撞机的尺寸。超级对撞机的尺寸定义为四个加速腔之一的长度。换言之，所构建的超级对撞机的尺寸定义为：两条线段交点到这两条线段任一端点的最短距离。若不存在相交的南北向与东西向轨道对，则无法建造超级对撞机，程序应报告最大尺寸为零。

Consider the example. There is one vertical line segment from (4, 0) to (4, 9) and two horizontal line segments: from (1, 1) to (9, 1) and from (1, 2) to (8, 2). The largest plus shape that can be found among these segments is formed from the only vertical segment and the second of horizontal segments, and is centered at (4, 2).

The program should output 2 because the closest end point of those segments to the center is (4, 0), which is distance 2 from the center point of (4, 2). The collider will be formed by the line segments from (2, 2) to (6, 2) and from (4, 0) to (4, 4).

考虑如下示例：存在一条从 $(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)$ 构成。