最小值最大考虑二分答案。
我们此时二分的答案为 \(X\)，注意到每条线段如果被计入答案那么肯定会对线段两端坐标有一定要求。我们先站在第一种 \(x=k\) 类型的线段进行考虑，如果这条线段能与另一种线段组合满足答案，那么另一种线段的 \(y\) 坐标的值显然必须满足 \(y_i+X\le y_j\le y_i+l_i-X\)。但是这远远不够，因为即使另一种线段的 \(y\) 坐标满足条件，在 \(x\) 坐标中， \(x_i\) 必须也要满足 \(x_j+X\le x_i\le x_j+l_j-X\)，\(j\) 表示与当前竖直线段组合的线段下标。这样有三维不能轻易用数据结构维护。然而我们发现每个横着的线段只在一段范围内能对竖直线段产生贡献，于是我们离散化 \(x\) 坐标，然后在 \(x_i\) 这里插入竖直线段所需的 \(y\) 坐标范围，我们之后要在这里询问，并且在 \(x_j+X\) 这里插入 \(y_j\)，在 \(x_j+l_j-X\) 移除 \(y_j\)，这样我们就可以用线段树维护这些操作了。
\(n\) 和 \(m\) 同级，时间复杂度 \(\mathcal{O}(n\log{n}\log{V}+n\log^2V)\)。
代码：
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; ++ i)
#define rrp(i, l, r) for (int i = r; i >= l; -- i)
#define eb emplace_back
#define inf 1000000000
#define linf 100000000000000
#define pii pair <int, int>
using namespace std;
constexpr int N = 2e5 + 5, P = 1e9 + 7;
inline int rd ()
{
int x = 0, f = 1;
char ch = getchar ();
while (! isdigit (ch)) { if (ch == '-') f = -1; ch = getchar (); }
while (isdigit (ch)) { x = (x << 1) + (x << 3) + ch - 48; ch = getchar (); }
return x * f;
}
int n, m;
class node
{
public:
int x, y, l;
friend bool operator < (const node &a, const node &b)
{
return a.x < b.x;
}
} c1[N], c2[N];
int li[N], len;
vector <int> v1[N], v2[N];
vector <pii> q[N];
int ls[N << 4], rs[N << 4], val[N << 4];
int rt, tot;
void upd (int &p, int l, int r, int x, int k)
{
if (! p) p = ++ tot;
if (l == r) return val[p] += k, void ();
int mid = l + r >> 1;
if (x <= mid) upd (ls[p], l, mid, x, k);
else upd (rs[p], mid + 1, r, x, k);
val[p] = val[ls[p]] + val[rs[p]];
}
int qry (int p, int l, int r, int L, int R)
{
if (L > R) return 0;
if (L <= l && r <= R) return val[p];
int mid = l + r >> 1, ret = 0;
if (L <= mid) ret += qry (ls[p], l, mid, L, R);
if (R > mid) ret += qry (rs[p], mid + 1, r, L, R);
return ret;
}
int check (int X)
{
len = 0;
rep (i, 1, n) li[++ len] = c1[i].x;
rep (i, 1, m) li[++ len] = c2[i].x + X, li[++ len] = c2[i].x + c2[i].l - X;
sort (li + 1, li + len + 1);
len = unique (li + 1, li + len + 1) - li - 1;
rep (i, 1, n)
{
int x = lower_bound (li + 1, li + len + 1, c1[i].x) - li;
q[x].eb (pii (c1[i].y + X, c1[i].y + c1[i].l - X));
}
rep (i, 1, m)
{
int x = lower_bound (li + 1, li + len + 1, c2[i].x + X) - li;
int y = lower_bound (li + 1, li + len + 1, c2[i].x + c2[i].l - X) - li;
if (x > y) continue;
v1[x].eb (c2[i].y);
v2[y].eb (c2[i].y);
}
int chk = 0;
rep (i, 1, len + 1)
{
for (auto v : v1[i]) upd (rt, -1e8, 2e8, v, 1);
for (auto p : q[i]) chk |= qry (1, -1e8, 2e8, p.first, p.second);
for (auto v : v2[i]) upd (rt, -1e8, 2e8, v, -1);
}
rep (i, 1, len + 1) v1[i].clear (), v2[i].clear (), q[i].clear ();
return chk;
}
int main ()
{
n = rd (), m = rd ();
rep (i, 1, n) c1[i].x = rd (), c1[i].y = rd (), c1[i].l = rd ();
rep (i, 1, m) c2[i].x = rd (), c2[i].y = rd (), c2[i].l = rd ();
sort (c1 + 1, c1 + n + 1);
int l = 0, r = 2e8, ans = 0;
while (l <= r)
{
int mid = l + r >> 1;
if (check (mid))
{
l = mid + 1; ans = mid;
} else r = mid - 1;
}
printf ("%d\n", ans);
}