## 1) Concise abridged problem statement

Given **n** distinct points \((x_i, y_i)\) \((4 \le n \le 20000)\) on the plane, find the **minimum integer \(d\)** such that all points can be covered (possibly on the border, squares may overlap) by **three axis-aligned squares**, each of size \(d \times d\).

Coordinates satisfy \(|x_i|, |y_i| \le 10^9\).

---

## 2) Detailed editorial (explaining the provided solution)

### Key idea: Binary search on the answer

If we can cover all points with 3 squares of side \(d\), then we can also do it for any larger side. So the predicate

> **possible(d)** = “cover all points with 3 axis-aligned \(d \times d\) squares”

is **monotone**, enabling **binary search** for the minimum \(d\).

We thus need an \(O(n)\) (or near) checker for a fixed \(d\).

The solution builds three checkers:

- `check_k1(S, d)`: can set \(S\) be covered by **1** square?
- `check_k2(S, d)`: can set \(S\) be covered by **2** squares?
- `check_k3(S, d)`: can set \(S\) be covered by **3** squares? (implemented using `check_k2`)

Each checker runs in \(O(|S|)\), so the whole decision is \(O(n)\). With binary search over a coordinate-sized range, total is \(O(n \log R)\).

---

### Covering with 1 square: `check_k1`

A set \(S\) fits in one \(d \times d\) axis-aligned square iff there exists a square \([X, X+d]\times[Y, Y+d]\) containing all points.

Equivalently:
- \(X \le x_i \le X+d \Rightarrow X \in [x_i-d, x_i]\)
- \(Y \le y_i \le Y+d \Rightarrow Y \in [y_i-d, y_i]\)

So \(X\) must belong to the intersection of all \([x_i-d, x_i]\), and similarly for \(Y\).
If both intersections are non-empty, one square suffices.

The code uses a “center style” equivalent trick by doubling coordinates:
- store feasible center ranges as \([2x_i-d, 2x_i+d]\) etc.
This avoids fractions when \(d\) is odd. Existence is still just checking intersections are non-empty.

---

### Covering with 2 squares: `check_k2`

Let \(S\) have bounding box:
- \(x \in [\min_x, \max_x]\)
- \(y \in [\min_y, \max_y]\)

A classic property used in this problem family:

> If \(S\) can be covered by two \(d \times d\) axis-aligned squares, then there exists a covering where the squares are placed on **opposite corners** of the bounding box (in one of the two diagonal pairings).

So we only need to test two configurations:

1. **Diagonal 1**: bottom-left + top-right  
   Squares:
   - BL candidate region: \([ \min_x, \min_x+d]\times[\min_y, \min_y+d]\)
   - TR candidate region: \([ \max_x-d, \max_x]\times[\max_y-d, \max_y]\)

   Every point must lie in at least one of these two squares.

2. **Diagonal 2**: bottom-right + top-left  
   Squares:
   - BR: \([ \max_x-d, \max_x]\times[\min_y, \min_y+d]\)
   - TL: \([ \min_x, \min_x+d]\times[\max_y-d, \max_y]\)

Again, verify each point is in at least one.

If either diagonal works, `check_k2` returns true.

Why this works (intuition): with 2 squares, extremes in x and y must be covered; pushing squares toward extremes (corners of the bounding box) never hurts feasibility because squares are axis-aligned and only need to include points, not avoid them.

---

### Covering with 3 squares: `check_k3`

For three squares, the solution tries to “peel off” one square anchored to a corner of the bounding box.

Compute \(\min_x,\max_x,\min_y,\max_y\) of the current set \(S\).
Consider placing the **first** square at one of the 4 corners:

- \((\min_x,\min_y)\)
- \((\max_x-d,\min_y)\)
- \((\min_x,\max_y-d)\)
- \((\max_x-d,\max_y-d)\)

For each placement:
1. Remove all points covered by that square.
2. Check if the remaining points can be covered by **2 squares** using `check_k2`.

If any corner placement works, `check_k3` is true.

Reasoning: In an optimal 3-square cover, at least one square can be shifted to touch the bounding box on both axes (otherwise you could move it outward without losing coverage). Trying the four corners covers those “tight” possibilities; the remaining points must then be coverable by two squares, which we can test.

---

### Complexity

For each \(d\):

- `check_k3`: computes bounding box \(O(n)\), tries 4 corners; each corner filters points \(O(n)\) and calls `check_k2` (also \(O(n)\)). Still \(O(n)\) overall with small constant (about up to ~8 passes).

Binary search over \(d\) in range ~ \(2\cdot 10^9\) ⇒ ~31 iterations.

Total: **\(O(n \log 2\cdot 10^9)\) ≈ \(O(31n)\)**, fine for \(n=20000\).

---

## 3) C++ Solution
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
vector<pair<int, int>> pnts;

void read() {
    cin >> n;
    pnts.resize(n);
    cin >> pnts;
}

bool check_k1(const vector<int>& indices, int64_t d) {
    if(indices.empty()) {
        return true;
    }
    int64_t left = -2e9, right = 2e9;
    int64_t bottom = -2e9, top = 2e9;
    for(int idx: indices) {
        int x = pnts[idx].first, y = pnts[idx].second;
        left = max(left, 2ll * x - d);
        right = min(right, 2ll * x + d);
        bottom = max(bottom, 2ll * y - d);
        top = min(top, 2ll * y + d);
    }
    return right >= left && top >= bottom;
}

bool check_k2(const vector<int>& indices, int64_t d) {
    if(indices.empty()) {
        return true;
    }

    int64_t min_x = 2e9, max_x = -2e9;
    int64_t min_y = 2e9, max_y = -2e9;
    for(int idx: indices) {
        min_x = min(min_x, (int64_t)pnts[idx].first);
        max_x = max(max_x, (int64_t)pnts[idx].first);
        min_y = min(min_y, (int64_t)pnts[idx].second);
        max_y = max(max_y, (int64_t)pnts[idx].second);
    }

    bool diag1 = true;
    for(int idx: indices) {
        int64_t x = pnts[idx].first, y = pnts[idx].second;
        bool in_bl = (x <= min_x + d && y <= min_y + d);
        bool in_tr = (x >= max_x - d && y >= max_y - d);
        if(!in_bl && !in_tr) {
            diag1 = false;
            break;
        }
    }
    if(diag1) {
        return true;
    }

    bool diag2 = true;
    for(int idx: indices) {
        int64_t x = pnts[idx].first, y = pnts[idx].second;
        bool in_br = (x >= max_x - d && y <= min_y + d);
        bool in_tl = (x <= min_x + d && y >= max_y - d);
        if(!in_br && !in_tl) {
            diag2 = false;
            break;
        }
    }
    return diag2;
}

bool check_k3(const vector<int>& indices, int64_t d) {
    if(indices.empty()) {
        return true;
    }

    int64_t min_x = 2e9, max_x = -2e9;
    int64_t min_y = 2e9, max_y = -2e9;
    for(int idx: indices) {
        min_x = min(min_x, (int64_t)pnts[idx].first);
        max_x = max(max_x, (int64_t)pnts[idx].first);
        min_y = min(min_y, (int64_t)pnts[idx].second);
        max_y = max(max_y, (int64_t)pnts[idx].second);
    }

    auto try_corner = [&](int64_t cx, int64_t cy) {
        vector<int> remaining;
        for(int idx: indices) {
            int64_t x = pnts[idx].first, y = pnts[idx].second;
            if(x < cx || x > cx + d || y < cy || y > cy + d) {
                remaining.push_back(idx);
            }
        }
        return check_k2(remaining, d);
    };

    return try_corner(min_x, min_y) || try_corner(max_x - d, min_y) ||
           try_corner(min_x, max_y - d) || try_corner(max_x - d, max_y - d);
}

void solve() {
    // One way to start with this problem is with a binary search on the answer.
    // We now want to check if a set of points S can be covered by 3 squares.
    // Let's have a function check(S, K) that equals true if we can cover S
    // using K squares.
    //
    // When K = 1, we can instead check the valid ranges of X and Y where the
    // square center can be. In particular if we have a point (x, y), then the
    // center should certainly be in the square defined by (x - D/2, y - D/2)
    // and (x + D/2, y + D/2). Then if there is a non-empty region, we are done.
    //
    // For K = 2, we can notice that there is always an optimal solution where
    // two squares are positioned at opposite corners of the bounding box. We
    // check both diagonal configurations: bottom-left + top-right, and
    // bottom-right + top-left. For each point, we verify it falls within at
    // least one of the two corner squares.
    //
    // For K = 3, we try placing the first square at each of the 4 corners of
    // the bounding box. For each placement, we mark the covered points and
    // recursively check if the remaining points can be solved with K = 2.
    // Since we try all 4 corners and K = 2 tries both diagonals, this covers
    // all possible configurations.
    //
    // The complexity is O(N log D) where D is the coordinate range, as each
    // check is O(N) and we binary search on the answer.

    vector<int> all_indices(n);
    iota(all_indices.begin(), all_indices.end(), 0);

    int64_t low = 0, high = 2000000042, mid, ret = high;
    while(low <= high) {
        mid = (low + high) / 2;
        if(check_k3(all_indices, mid)) {
            ret = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    cout << ret << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 4) Python solution (same approach) with detailed comments

```python
import sys
from typing import List, Tuple

# We'll implement the same structure: check_k2, check_k3, and binary search.
# (check_k1 is not needed for this particular implementation, but included
# for completeness / parity with the C++ idea.)

def check_k1(points: List[Tuple[int, int]], idxs: List[int], d: int) -> bool:
    """
    Can the indexed points be covered by ONE d x d square?
    Use doubled-center intersection method to avoid fractions.
    """
    if not idxs:
        return True

    left, right = -2_000_000_000, 2_000_000_000   # feasible range for 2*cx
    bottom, top = -2_000_000_000, 2_000_000_000   # feasible range for 2*cy

    for i in idxs:
        x, y = points[i]
        left = max(left, 2 * x - d)
        right = min(right, 2 * x + d)
        bottom = max(bottom, 2 * y - d)
        top = min(top, 2 * y + d)

    return right >= left and top >= bottom


def check_k2(points: List[Tuple[int, int]], idxs: List[int], d: int) -> bool:
    """
    Can the indexed points be covered by TWO d x d squares?
    Try the two diagonal-corner configurations w.r.t. bounding box.
    """
    if not idxs:
        return True

    # Bounding box
    min_x = min(points[i][0] for i in idxs)
    max_x = max(points[i][0] for i in idxs)
    min_y = min(points[i][1] for i in idxs)
    max_y = max(points[i][1] for i in idxs)

    # Diagonal 1: bottom-left + top-right
    ok = True
    for i in idxs:
        x, y = points[i]
        in_bl = (x <= min_x + d and y <= min_y + d)
        in_tr = (x >= max_x - d and y >= max_y - d)
        if not (in_bl or in_tr):
            ok = False
            break
    if ok:
        return True

    # Diagonal 2: bottom-right + top-left
    ok = True
    for i in idxs:
        x, y = points[i]
        in_br = (x >= max_x - d and y <= min_y + d)
        in_tl = (x <= min_x + d and y >= max_y - d)
        if not (in_br or in_tl):
            ok = False
            break

    return ok


def check_k3(points: List[Tuple[int, int]], idxs: List[int], d: int) -> bool:
    """
    Can the indexed points be covered by THREE d x d squares?
    Try placing one square at each corner of the bounding box, then reduce to k=2.
    """
    if not idxs:
        return True

    # Bounding box
    min_x = min(points[i][0] for i in idxs)
    max_x = max(points[i][0] for i in idxs)
    min_y = min(points[i][1] for i in idxs)
    max_y = max(points[i][1] for i in idxs)

    def try_corner(cx: int, cy: int) -> bool:
        # Collect points not covered by square [cx,cx+d] x [cy,cy+d]
        rem = []
        for i in idxs:
            x, y = points[i]
            if x < cx or x > cx + d or y < cy or y > cy + d:
                rem.append(i)
        return check_k2(points, rem, d)

    # Try the four corners (adjusting by d to keep square aligned with bbox extremes)
    return (
        try_corner(min_x, min_y) or
        try_corner(max_x - d, min_y) or
        try_corner(min_x, max_y - d) or
        try_corner(max_x - d, max_y - d)
    )


def solve() -> None:
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    points = []
    it = iter(data[1:])
    for xs, ys in zip(it, it):
        points.append((int(xs), int(ys)))

    idxs = list(range(n))

    # Binary search on d (same upper bound idea as C++)
    lo, hi = 0, 2_000_000_042
    ans = hi
    while lo <= hi:
        mid = (lo + hi) // 2
        if check_k3(points, idxs, mid):
            ans = mid
            hi = mid - 1
        else:
            lo = mid + 1

    sys.stdout.write(str(ans) + "\n")


if __name__ == "__main__":
    solve()
```

---

## 5) Compressed editorial

Binary search the minimal side length \(d\) since feasibility is monotone.

For a fixed \(d\), decide if points can be covered by 3 squares:

- `k=2`: compute bounding box \([\min_x,\max_x]\times[\min_y,\max_y]\). It suffices to test only two configurations: squares anchored at opposite corners (BL+TR or BR+TL). Check each point lies in at least one of the two corner squares.
- `k=3`: compute bounding box; try placing one square at each of the 4 corners of the bounding box (with corner coordinates adjusted by \(d\) where needed). Remove covered points and test the remainder with the `k=2` check.

Each check is \(O(n)\); binary search adds a factor \(\log(2\cdot 10^9)\approx 31\). Total \(O(n\log R)\).