Subtask 1:Với n=~4~,thì để ~3~ hình vuông bao được ~4~ điểm thì sẽ có ít nhất ~1~ hình vuông bao ~2~ điểm trong ~4~ điểm trên nên ta có thể xét các trường hợp ~2~ điểm được bao và sẽ tính được diện tích hình vuông nhỏ nhất bao ~2~ điểm này còn ~2~ điểm còn lại mỗi điểm chỉ cần một hình vuông diện tích độ dài ~1~ để bao chúng.Từ đó ta sẽ tính được kết quả của bài toán.

Subtask 2:Sinh mọi cấu hình có thể với mỗi điểm thuộc  n  điểm đã cho, với mỗi điểm có thể có  3  trường hợp là nó có thể thuộc hình vuông thứ ~1,2,3~.

Với mỗi trường hợp sinh được ta có thể tính được độ dài cạnh nhỏ nhất của mỗi hình vuông mà bao các điểm ta đã sinh cấu hình.Từ đó ta tìm được kết quả của bài toán.

Độ phức tạp: O(~3^n~);

Subtask 3:Ta có  4  điểm có tung độ và hoành độ lớn nhất và nhỏ nhất là ~4~ điểm biên của tập điểm.Để ~3~ hình vuông bao cả tập điểm này thì sẽ có ít nhất ~1~ hình vuông bao ~2~ điểm kề nhau trong ~4~ điểm này.Ta có thể chặt nhị phân đáp án và từ quan sát trên ta xét các trường hợp có thể và tìm ra đáp án tối ưu.

Độ phức tạp: O(~n \times log_2{n}~);

#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;
}

const int INF = 1e9;

using pt = pair<int, int>;

bool between(int p, int l, int r) {
    return l <= p && p <= r;
}

vector<int> extremes(const vector<pt> &pts) {
    int min_x = INF, min_y = INF;
    int max_x = -INF, max_y = -INF;
    for (auto p : pts) {
        cmin(min_x, p.first);
        cmax(max_x, p.first);
        cmin(min_y, p.second);
        cmax(max_y, p.second);
    }
    return vector<int>({min_x, max_x, min_y, max_y});
}

bool check(const vector<pt> &pts, int d, int k) {
    if (pts.size() <= k) return true;
    auto ex = extremes(pts);
    if (k == 1) {
        return ex[1] - ex[0] <= d && ex[3] - ex[2] <= d;
    }
    for (int i = 0; i < 2; i++) {
        int lx = ex[i] - d * (i == 1);
        int rx = ex[i] + d * (i == 0);
        for (int j = 2; j < 4; j++) {
            int ly = ex[j] - d * (j == 3);
            int ry = ex[j] + d * (j == 2);
            vector<pt> new_pts;
            for (auto p : pts) {
                if (!between(p.first, lx, rx) || !between(p.second, ly, ry))
                    new_pts.push_back(p);
            }
            if (check(new_pts, d, k - 1)) return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<pt> pts(n);
    for (auto &p : pts) {
        cin >> p.first >> p.second;
    }
    auto ex = extremes(pts);
    long long ld = 1, rd = 2e9;
    while (ld < rd) {
        long long md = ld + (rd - ld) / 2;
        if (check(pts, md, 3)) {
            rd = md;
        } else {
            ld = md + 1;
        }
    }
    cout << 1LL*ld*ld;
}