## 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) Provided C++ solution with detailed line-by-line comments

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

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

// Input a pair: reads first then second
template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

// Input a vector: reads all elements in order
template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for (auto& x : a) {
        in >> x;
    }
    return in;
};

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

int n;                          // number of points
vector<pair<int, int>> pnts;    // list of points (x, y)

void read() {
    cin >> n;                   // read n
    pnts.resize(n);             // allocate storage
    cin >> pnts;                // read all points using the vector>> overload
}

/*
check_k1(indices, d):
Returns true iff the points indexed by "indices" can be covered by ONE d x d square.

This implementation uses doubled coordinates to avoid dealing with half-integers:
For a point (x, y), the square center (cx, cy) must satisfy:
|cx - x| <= d/2 and |cy - y| <= d/2.
Multiply by 2:
|2cx - 2x| <= d  =>  2cx in [2x - d, 2x + d]
Similarly for y.
So we intersect all these ranges for 2cx and 2cy.
*/
bool check_k1(const vector<int>& indices, int64_t d) {
    if (indices.empty()) {
        return true;            // empty set is trivially coverable
    }

    // Start with huge feasible intervals for doubled center coordinates
    int64_t left = -2e9, right = 2e9;   // feasible range for 2*cx
    int64_t bottom = -2e9, top = 2e9;   // feasible range for 2*cy

    for (int idx : indices) {
        int x = pnts[idx].first, y = pnts[idx].second;

        // Intersect with this point's allowed center range
        left   = max(left,   2ll * x - d);
        right  = min(right,  2ll * x + d);
        bottom = max(bottom, 2ll * y - d);
        top    = min(top,    2ll * y + d);
    }

    // Non-empty intersection on both axes means feasible center exists
    return right >= left && top >= bottom;
}

/*
check_k2(indices, d):
Returns true iff points can be covered by TWO d x d squares.

The solution checks two "diagonal corner" configurations with respect to the
bounding box of the points: (BL + TR) or (BR + TL).
*/
bool check_k2(const vector<int>& indices, int64_t d) {
    if (indices.empty()) {
        return true;
    }

    // Compute bounding box of the subset
    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);
    }

    // Try diagonal configuration 1: bottom-left + top-right
    bool diag1 = true;
    for (int idx : indices) {
        int64_t x = pnts[idx].first, y = pnts[idx].second;

        // In bottom-left corner square anchored at (min_x, min_y)
        bool in_bl = (x <= min_x + d && y <= min_y + d);

        // In top-right corner square anchored at (max_x - d, max_y - d)
        bool in_tr = (x >= max_x - d && y >= max_y - d);

        // Must be in at least one of the two squares
        if (!in_bl && !in_tr) {
            diag1 = false;
            break;
        }
    }
    if (diag1) {
        return true; // success with diagonal 1
    }

    // Try diagonal configuration 2: bottom-right + top-left
    bool diag2 = true;
    for (int idx : indices) {
        int64_t x = pnts[idx].first, y = pnts[idx].second;

        // Bottom-right square anchored at (max_x - d, min_y)
        bool in_br = (x >= max_x - d && y <= min_y + d);

        // Top-left square anchored at (min_x, max_y - d)
        bool in_tl = (x <= min_x + d && y >= max_y - d);

        if (!in_br && !in_tl) {
            diag2 = false;
            break;
        }
    }
    return diag2; // true if diagonal 2 works
}

/*
check_k3(indices, d):
Returns true iff points can be covered by THREE d x d squares.

Strategy:
- Take bounding box of current set.
- Try placing the first square at each of the 4 corners of that bounding box.
- Remove covered points, and check if remaining can be covered by 2 squares
  (check_k2).
*/
bool check_k3(const vector<int>& indices, int64_t d) {
    if (indices.empty()) {
        return true;
    }

    // Compute bounding box
    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);
    }

    // Helper: place one square with bottom-left corner (cx, cy),
    // keep points not covered, and see if remaining fits in 2 squares.
    auto try_corner = [&](int64_t cx, int64_t cy) {
        vector<int> remaining;
        remaining.reserve(indices.size());

        for (int idx : indices) {
            int64_t x = pnts[idx].first, y = pnts[idx].second;

            // If point is outside [cx, cx+d] x [cy, cy+d], it remains
            if (x < cx || x > cx + d || y < cy || y > cy + d) {
                remaining.push_back(idx);
            }
        }
        return check_k2(remaining, d);
    };

    // Try all 4 corners of the bounding box (adjusted by d where needed)
    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() {
    // Build an index list [0..n-1] so checkers can operate on subsets easily.
    vector<int> all_indices(n);
    iota(all_indices.begin(), all_indices.end(), 0);

    // Binary search over d. Upper bound is chosen large enough to cover all.
    int64_t low = 0, high = 2000000042, mid, ret = high;

    while (low <= high) {
        mid = (low + high) / 2;

        // If we can cover with 3 squares of side mid, try smaller
        if (check_k3(all_indices, mid)) {
            ret = mid;
            high = mid - 1;
        } else {
            // Otherwise need bigger squares
            low = mid + 1;
        }
    }

    cout << ret << '\n'; // minimal d found
}

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

    int T = 1;
    // cin >> T;  // problem has a single test; left here as template
    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)\).