まず、最終的に全員が集まるマスを固定したときの問題を考えます。

全員がマス \((R, C)\) に集まる時刻として考えられる最小値は \(\displaystyle\max_{i = 1, 2, \ldots, N}( \max(|R-R_i|, |C-C_i|))\) です。これは、各人がマス \((R, C)\) にいない限り、\(1\) 回の移動で \( \max(|R-R_i|, |C-C_i|)\) を \(1\) 小さくできることができ、また \(2\) 以上小さくできることはないことからわかります。

\(R_i\) の最大値、最小値を \(R_{max}, R_{min}\)、\(C_i\) の最大値、最小値を \(C_{max}, C_{min}\) とすると\(\displaystyle\max_{i = 1, 2, \ldots, N}( \max(|R-R_i|, |C-C_i|)) = \max(|R - R_{max}|, |R-R_{min}|, |C-C_{max}|, |C-C_{min}|)\) です。

したがって、\(1 \leq R, C \leq 10^9\) を満たす整数 \(R, C\) について \(\max(|R - R_{max}|, |R-R_{min}|, |C-C_{max}|, |C-C_{min}|)\) の最小値が本問題の答えとなります。

この値を求めるには \(\max(|R - R_{max}|, |R-R_{min}|)\) の最小値および \(\max(|C-C_{max}|, |C-C_{min}|)\) の最小値をそれぞれ求めればよく、これは \(R = \lfloor\frac{R_{max} + R_{min}}{2}\rfloor, C = \lfloor\frac{C_{max} + C_{min}}{2}\rfloor\) が最小値を与える \(R, C\) （の \(1\) つ）となります。

また、具体的な \(\max(|R - R_{max}|, |R-R_{min}|)\) の最小値は \(\lceil\frac{R_{max} - R_{min}}{2}\rceil\)、\(\max(|C - C_{max}|, |C-C_{min}|)\) の最小値は \(\lceil\frac{C_{max} - C_{min}}{2}\rceil\) となります。

実装例

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> x(n), y(n);
	for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
	int X = *max_element(x.begin(), x.end()) - *min_element(x.begin(), x.end());
	int Y = *max_element(y.begin(), y.end()) - *min_element(y.begin(), y.end());
	int ans = (max(X, Y) + 1) / 2;
	cout << ans << '\n';
}