Trong tối đa ~t~ giây, người thứ ~i~ ở vị trí ~(x_i, y_i)~ sẽ tới được các vị trí tạo thành một hình vuông, giới hạn bởi ô góc trái dưới ~(x_i - t, y_i - t)~ và góc phải trên ~(x_i + t, y_i + t)~. Xét hình chữ nhật mà ~n~ hình vuông này giao nhau. Nếu hình chữ nhật này nằm trọn trong các vùng đất nguyền rủa thì ta không thể chọn ra vị trí ~(a, b)~ thoả mãn, ta phải tăng giới hạn ~t~ giây lên. Ngược lại ta có thể xét thời gian ~t~ nhỏ hơn.

Gọi hình chữ nhật mà ~n~ hình vuông giao nhau là ~S~.

Subtask ~1~:

Vì ~m = 1~ nên ta chỉ cần tìm phần giao của ~S~ với vùng đất nguyền rủa để kiểm tra.

Độ phức tạp: ~O(n \times \log(10^9))~.

Subtask ~2~:

Ta có thể bao hàm loại trừ để tính diện tích giao nhau giữa ~S~ và các vùng đất nguyền rủa. Gọi ~f(mask)~ là diện tích phần giao của ~S~ và các vùng đất thuộc ~mask~. Ta có:

~f(\{1, 2, ..., m\})~ = ~f(\{1\})~ + ~f(\{2\})~ + ... + ~f(\{m\})~ - ~f(\{1, 2\})~ - ~f(\{1, 3\})~ - ... - ~f(\{m - 1, m\})~ + ~f(\{1, 2, 3\})~ + ...

Độ phức tạp: ~O(\log(10^9) \times (n + 2^m))~.

Subtask ~3~:

Ta dùng kĩ thuật sweepline để kiểm tra ~S~ có hoàn toàn bị bao phủ hay không. Đầu tiên ta phải rời rạc hoá toạ độ. Vùng đất nguyền rủa thứ ~i~ sẽ ảnh hưởng các hàng ~[d_i, f_i]~ trong khoảng các cột ~[c_i, e_i]~. Ta có thể xét lần lượt các cột và cập nhật các hàng bị ảnh hưởng. Nếu một cột của ~S~ bị bao phủ tất cả các hàng thì không tồn tại ô ~(a, b)~ nào thoả mãn. Mỗi lần thêm đoạn hoặc xoá đoạn đi, ta phải cập nhật các hàng bị bao phủ. Vì ~m~ nhỏ nên ta chỉ cần duyệt trâu thay vì sử dụng CTDL.

ĐPT: ~O(\log(10^9) \times (n + m \times m))~.

Subtask ~4~:

Ta dùng CTDL Segtree để tối ưu subtask ~3~.

Độ phức tạp: ~O(\log(10^9) \times (n + m \times \log(n)))~.

Code mẫu

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

template <class X, class Y>
bool cmin(X &a, const Y &b) {
  return a > b ? a = b, 1 : 0;
}

template <class X, class Y>
bool cmax(X &a, const Y &b) {
  return a < b ? a = b, 1 : 0;
}

struct event {
  int x, l, r, t;

  event(int x, int l, int r, int t): x(x), l(l), r(r), t(t) {}

  bool operator < (const event &o) const {
    return x != o.x ? x < o.x : t < o.t;
  }
};

const int N = 100005;
const int INF = 1e9 + 1;

int cover[N * 4], lazy[N * 4];

void add(int i, int l, int r, int x, int y, int v) {
#define il i + 1
#define ir i + (m - l) * 2
  if (l >= x && r <= y) {
    cover[i] += v; lazy[i] += v; return;
  }
  int m = (l + r) / 2;
  if (m > x) add(il, l, m, x, y, v);
  if (m < y) add(ir, m, r, x, y, v);
  cover[i] = min(cover[il], cover[ir]) + lazy[i];
#undef il
#undef ir
}

int X[N], Y[N], X1[N], Y1[N], X2[N], Y2[N];
int n, m; vector<int> coor; vector<event> all;

bool check(int mid) {
  coor.clear(); all.clear();
  int x1 = -INF, y1 = -INF, x2 = INF, y2 = INF;
  for (int i = 0; i < n; i++) {
    cmax(x1, X[i] - mid); cmax(y1, Y[i] - mid);
    cmin(x2, X[i] + mid); cmin(y2, Y[i] + mid);
  }
  if (x1 > x2 || y1 > y2) return false;
  coor.push_back(y1);
  coor.push_back(y2 + 1);
  all.emplace_back(x1, y1, y2 + 1, INF);
  all.emplace_back(x2 + 1, y1, y2 + 1, -INF);
  for (int i = 0; i < m; i++) {
    int tx1 = max(x1, X1[i]);
    int ty1 = max(y1, Y1[i]);
    int tx2 = min(x2, X2[i]);
    int ty2 = min(y2, Y2[i]);
    if (tx1 <= tx2 && ty1 <= ty2) {
      coor.push_back(ty1);
      coor.push_back(ty2 + 1);  
      all.emplace_back(tx1, ty1, ty2 + 1, 1);
      all.emplace_back(tx2 + 1, ty1, ty2 + 1, -1);
    }
  }

  sort(coor.begin(), coor.end());

  coor.erase(unique(coor.begin(), coor.end()), coor.end());
  sort(all.begin(), all.end());
  memset(cover, 0, sizeof cover);
  memset(lazy, 0, sizeof lazy);
  for (int i = 0; i < all.size(); ) {
    int j = i;
    while (j < all.size() && all[j].x == all[i].x) {
      int l = lower_bound(coor.begin(), coor.end(), all[j].l) - coor.begin();
      int r = lower_bound(coor.begin(), coor.end(), all[j].r) - coor.begin();
      add(1, 0, coor.size() - 1, l, r, all[j].t); j++;
    }
    if (cover[1] == INF) return true; i = j;
  }
  return false;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    cin >> X[i] >> Y[i];
  for (int i = 0; i < m; i++)
    cin >> X1[i] >> Y1[i] >> X2[i] >> Y2[i];
  int low = 0, high = 1e9 + 1;
  while (low < high) {
    int mid = (low + high) / 2;
    if (check(mid)) high = mid;
    else low = mid + 1;
  }
  cout << high;
}