First, consider the case where the final destination is fixed.

If they are to meet at \((R, C)\), the earliest possible time is \(\displaystyle\max_{i = 1, 2, \ldots, N}( \max(|R-R_i|, |C-C_i|))\). This is because, whenever each person is not at \((R, C)\), they can reduce \( \max(|R-R_i|, |C-C_i|)\) by one in a move, but not by two.

Let \(R_{max}\) and \(R_{min}\) be the maximum and minimum values of \(R_i\), and \(C_{max}\) and \(C_{min}\) be the maximum and minimum values of \(C_i\). Then \(\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}|)\).

Therefore, the answer to the original problem is the minimum value of \(\max(|R - R_{max}|, |R-R_{min}|, |C-C_{max}|, |C-C_{min}|)\) among all integers \(R\) and \(C\) with \(1 \leq R, C \leq 10^9\).

To find this value, it is sufficient to find the minimum possible \(\max(|R - R_{max}|, |R-R_{min}|)\) and the minimum possible \(\max(|C-C_{max}|, |C-C_{min}|)\). In fact, \(R = \lfloor\frac{R_{max} + R_{min}}{2}\rfloor\) and \(C = \lfloor\frac{C_{max} + C_{min}}{2}\rfloor\) are (examples of) the values \(R\) and \(C\) that yield the minimum value.

The actual minimum value for \(\max(|R - R_{max}|, |R-R_{min}|)\) is \(\lceil\frac{R_{max} - R_{min}}{2}\rceil\), and that for\(\max(|C - C_{max}|, |C-C_{min}|)\) is \(\lceil\frac{C_{max} - C_{min}}{2}\rceil\).

Sample code

#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';
}