← 返回题目列表

Codeforces · 391/D1

D1. 超级对撞机

中文机器翻译题面 查看原题

该问题由两个子问题组成:解决子问题 D1,您将获得 3 分,解决子问题 D2,您将获得 16 分。

Manao 是参与规划新型超级对撞机的首席建筑师。他必须确定一块可以建造最大的超级对撞机的土地。他正在建造的超级对撞机需要以相同速度行进的粒子进行四向正交碰撞,因此它将由四个加速室组成,形状像一个加号(即+)。四个加速室中的每一个都必须具有相同的长度,并且必须与地球磁场对齐(平行或正交),以尽量减少干扰。

加速室需要铺设在长而平坦的土地上,以控制成本。因此,马瑙已经委托进行了一项地形研究,确定了可用于建造与地球磁场平行或正交的加速室的所有可能的最大长度土地。为了建造尽可能最大的超级对撞机,马瑙必须从这些候选区域中找出最大的对称加号形状。也就是说,他必须找到两块土地,形成一个轴对齐的加号形状,并且从加号的中心到加号的四个臂中最短的尖端的距离最大。请注意,对撞机不需要使用已识别区域的整个长度(请参阅注释中的示例)。

输入

输入的第一行将包含两个单空格分隔的整数 n(南北向地区的数量)和 m(东西向地区的数量)。

第一行之后的 n 行中的每一行都描述了一个南北走向的区域。每个这样的区域由三个单空格分隔的整数 xi, yi, li 描述,表示从 (xi, yi) 到 (xi, yi + li) 的垂直线段。

类似地,在描述南北区域的 n 条线之后,紧随描述东西区域的 m 条类似线。每个这样的区域由三个单空格分隔的整数 xi、yi、li 描述,表示从 (xi, yi) 到 (xi + li, yi) 的水平线段。

所有 xi 和 yi 都在 -100000000 和 100000000 之间(包含 -100000000 和 100000000)。所有 li 都在 1 到 100000000 之间(包含 1 和 100000000)。没有一对水平线段会接触或相交,也没有一对垂直线段会接触或相交。

该问题由两个子问题组成。子问题对输入有不同的约束。正确提交子问题将获得一些分数。子问题的描述如下。

- 在子问题 D1(3 点)中,n 和 m 将介于 1 和 1000 之间(包含 1 和 1000)。
- 在子问题 D2(16 点)中,n 和 m 将介于 1 和 50000 之间(包含 1 和 50000)。

输出

打印一行,其中包含一个整数,即可以在一个南北向区域和一个东西向区域上建造的最大超级对撞机的大小。超级对撞机的尺寸定义为四个加速室之一的长度。换句话说,生成的超级对撞机的大小定义为从两条线段的交点到两条线段中任一线段的最近端点的距离。如果没有一对南北向和东西向区域相交,则不可能建造超级对撞机,并且程序应报告最大尺寸为零。

示例

输入 #1

1 2
4 0 9
1 1 8
1 2 7

输出 #1

2

注意

考虑这个例子。从(4, 0)到(4, 9)有一条垂直线段,从(1, 1)到(9, 1)和(1, 2)到(8, 2)有两条水平线段。在这些线段中可以找到的最大加号形状由唯一的垂直线段和第二个水平线段形成,并以 (4, 2) 为中心。

程序应该输出 2,因为这些线段距离中心最近的端点是 (4, 0),距离 (4, 2) 的中心点为 2。碰撞体将由从 (2, 2) 到 (6, 2) 和 (4, 0) 到 (4, 4) 的线段形成。