We have no time to compute each of the \(\frac{N(N-1)}{2}\) distances and sort them in \(O(N^2 \log N)\) time.

Let us make more use of the property of the distance. Consider finding the following:

• The greatest difference in \(x\)-coordinates of two houses
• The greatest difference in \(y\)-coordinates of two houses
• The second greatest difference in \(x\)-coordinates of two houses
• The second greatest difference in \(y\)-coordinates of two houses

We can easily find the first two of them, and the second greatest difference in \(x\)-coordinates is one of the following:

• The second largest \(x\)-coordinate minus the smallest \(x\)-coordinate
• The largest \(x\)-coordinate minus the second smallest \(x\)-coordinate

We can find the second greatest difference in \(y\)-coordinates similarly.

Now, can we just print the second greatest value among the four differences? Unfortunately, it could be incorrect if the same pair of houses appears twice among them.

To fix this issue, let us list all houses that appear in these four pairs, and find the distance between every pair of houses in the list. Since the list will contain at most \(8\) houses, an efficient implementation will work in \(O(N)\) time, which is fast enough.

Sample Implementation (C++)

#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
using ll = long long;
using namespace std;

const char EOLN = '\n';

int n;
vector<vector<int>> a;
set<int> ids;
int main()
{
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    int x, y;
    cin >> x >> y;
    a.emplace_back(vector<int>{x, y, i});
  }
  for (int k = 0; k < 2; k++)
  {
    sort(a.begin(), a.end());
    for (int i = 0; i < 2; i++)
    {
      ids.emplace(a[i][2]);
      ids.emplace(a[n - 1 - i][2]);
    }
    for (auto &v : a)
      swap(v[0], v[1]);
  }

  vector<pair<int, int>> b;
  for (auto v : a)
    if (ids.count(v[2]) != 0)
      b.emplace_back(v[0], v[1]);
  vector<ll> d;
  for (int i = 0; i < b.size(); i++)
    for (int j = i + 1; j < b.size(); j++)
      d.emplace_back(max(abs(b[i].first - b[j].first), abs(b[i].second - b[j].second)));
  sort(d.begin(), d.end());
  cout << d[d.size() - 2] << endl;
  return 0;
}