条件に単調性があるので、\(X\) を決め打って判定することで二分探索する（決め打ち二分探索）ことができます。

いわゆる 45度回転 を行います。

\[z_i = x_i + y_i\]

\[w_i = x _i- y_i\]

とすると、

\[ \begin{aligned} &|x_1-x_2| + |y_1-y_2| \ge X\\ \Leftrightarrow & |z_1 - z_2| \ge X ~ \text{or} ~ |w_1 - w_2| \ge X \end{aligned} \]

となります。 \(|z_i - z_j| \ge X\) となっているところに \(i, j\) の辺を張り、 \(|w_i - w_j| \ge X\) となっているところに \(i, j\) の辺を張ったグラフが連結かどうかを見ればよいです。

1. 区間に辺を張るテクニック

区間に辺を張るテクニックを用いて強連結成分分解 (SCC) すれば解けます。計算量は全体で \(O(N (\log N + \log (\max x, \max y)))\) です（グラフの辺数は \(O(N)\) になる）。

2. 工夫したグラフ

ただ、今回の問題はもう少し簡単に解けます。

• \(z_i\) の最小値を点 \(a\) が取り、最大値を \(b\) が取るとする。
• \(w_i\) の最小値を点 \(c\) が取り、最大値を \(d\) が取るとする。
• \(|z_i - z_a| \ge X\) なら \(i, a\) 間に辺を張る
• \(|z_i - z_b| \ge X\) なら \(i, b\) 間に辺を張る
• \(|w_i - w_c| \ge X\) なら \(i, c\) 間に辺を張る
• \(|w_i - w_d| \ge X\) なら \(i, d\) 間に辺を張る

こうしたグラフで連結かどうかを判定することが同値になります。

証明：\(z\) のみに注目します。 \(z_i < z_j\) 、 \(|z_i - z_j| \ge X\) なら \(|z_i - z_b| \ge X\) かつ \(|z_a - z_j| \ge X\) かつ \(|z_a - z_b| \ge X\) であるので連結になります。しかし、このグラフは元のグラフの部分グラフです。以上より、連結性は変わりません。

計算量は変わらず全体で \(O(N (\log N + \log (\max x, \max y)))\) ですが、実装は非常に簡潔です。