Отсортируем точки по возрастанию $x$.

Сделаем бинпоиск по ответу ($k$). $min(|x_i-x_j|,|y_i-y_j|)\ge k\to |x_i-x_j|\ge k\text{ and }|y_i-y_j|\ge k$

• Попробуем сделать проверку за $O(n)$.

Пусть $i$ текущий индекс в массиве. Пусть $j<i\to x_j\le x_i$.

Значит раскрывая модуль получаем $x_j\le x_i-k\text{ and }|y_i-y_j|\ge k$. С помощью двух указателей будем передвигать $j$, чтобы у всех точек до $j$-ой как минимум первое условие выполнялось.

Тогда условие стало ещё проще $|y_i-y_{0\dots j}|\ge k=max(|y_i-y_{0\dots j}|)\ge k$ Просто раскрыв модуль, получаем, что надо просто хранить самую верхнюю точку по $y$ и самую нижнюю по $y$.

const int INF = INT_MAX;
int n;
vector<pair<int, int>> xy;

bool check(int k) {
  int j = 0;
  int mxy = -INF;
  int mny = INF;
  for (int i = 0; i < n; i++) {
    while (j < n && xy[j].first <= xy[i].first - k) {
      mxy = max(mxy, xy[j].second);
      mny = min(mny, xy[j].second);
      j++;
    }
    if (mny != INF && xy[i].second - mny >= k) return true;
    if (mxy != -INF && mxy - xy[i].second >= k) return true;
  }
  return false;
}

void solve() {
  cin >> n;
  xy.assign(n, {0, 0});
  for (int i = 0; i < n; i++) cin >> xy[i].first >> xy[i].second;
  sort(xy.begin(), xy.end());
  int l = 0, r = 2e9 + 7;
  while (r - l > 1) {
    int mid = (l + r) >> 1;
    if (check(mid)) {
      l = mid;
    } else {
      r = mid;
    }
  }
  cout << l;
}