Submission #25241998

---

Source Code Expand

#include <iostream>
#include <algorithm>
using namespace std;

int N;
using T = pair<long long, long long>;
using S = pair<T, int>;
T P[200005];
S Q[200005], R[200005];

long long d(int i, int j) {
  return min(abs(P[i].first - P[j].first), abs(P[i].second - P[j].second));
}

int main() {
  cin >> N;
  for (int i = 0; i < N; i++) { cin >> P[i].first >> P[i].second; }
  long long ans = 0;

  for (int i = 0; i < N; i++) {
    Q[i] = { {P[i].first + P[i].second, P[i].first - P[i].second}, i };
    R[i] = { {P[i].first + P[i].second, P[i].first - P[i].second}, i };
  }

  sort(Q, Q+N, [](S&a, S&b) { return a.first.first < b.first.first; });
  sort(R, R+N, [](S&a, S&b) { return a.first.second < b.first.second; });
  // for (int i = 0; i < N; i++) { printf("Q[%d] = ((%lld, %lld), %d)\n", i, Q[i].first.first, Q[i].first.second, Q[i].second); }
  for (int i = 0; i < max(2, N/30); i++) {
    for (int j = 0; j < max(2, N/30); j++) {
      ans = max(ans, d(Q[i].second, Q[N-1-j].second));
      ans = max(ans, d(Q[i].second, R[N-1-j].second));
      ans = max(ans, d(R[i].second, Q[N-1-j].second));
      ans = max(ans, d(R[i].second, R[N-1-j].second));

      ans = max(ans, d(Q[i].second, Q[N/2-1-j].second));
      if (N/2-1+j < N) { ans = max(ans, d(Q[i].second, Q[N/2-1+j].second)); }
      if (N/2-i >= 0) { ans = max(ans, d(Q[N/2-i].second, Q[N-1-j].second)); }
      ans = max(ans, d(Q[N/2+i].second, Q[N-1-j].second));
    }
  }

  cout << ans << endl;
}

Submission Info

Judge Result