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

const long long INF = 1e18;
int N;
struct Pt { long long x, y; };
vector<Pt> a;

// dp[i][j] là tổng bình phương tọa độ của i điểm được chọn lên trục thứ j
// Trạng thái: tổng bình phương tọa độ Ox được chọn và Oy được chọn
map<pair<long long, long long>, long long> dp;

int main() {
    cin >> N;
    a.resize(N);
    for(int i=0; i<N; i++) cin >> a[i].x >> a[i].y;

    dp[{0, 0}] = 0;

    for(int i=0; i<N; i++) {
        map<pair<long long, long long>, long long> next_dp;
        for(auto &state : dp) {
            long long sum_x = state.first.first;
            long long sum_y = state.first.second;
            long long cost = state.second;

            // Chọn đưa lên Ox
            long long new_sum_x = sum_x + a[i].x * a[i].x;
            long long new_cost_x = cost + a[i].x * a[i].x;
            // ... (Logic này không hoàn toàn đúng trong bài toán Maximization)
            // Lưu ý: Bài toán này về bản chất là Minimize Max(Các bình phương)
            // DP thông thường tính tổng không giải quyết được trực tiếp bài toán Min-Max
        }
    }
    // ... code mẫu bị thiếu ...
}

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

using int64 = long long;
struct Pt { int64 x, y; };
int N;
vector<Pt> a;

inline int node(int i, int val){ return (i<<1) | (val&1); }
inline int neg(int u){ return u ^ 1; }

void addImp(vector<vector<int>>& g, int u, int v){ g[u].push_back(v); }

// Hàm kiểm tra tính khả thi với biên M
bool feasible(int64 M){
    vector<vector<int>> g(2*N);

    for(int i=0; i<N; i++){
        for(int j=i+1; j<N; j++){
            // Tính bình phương khoảng cách giữa các cặp điểm có thể
            // Dùng __int128 để tránh tràn số khi nhân
            __int128 d_xx = (__int128)(a[i].x - a[j].x) * (a[i].x - a[j].x);
            __int128 d_yy = (__int128)(a[i].y - a[j].y) * (a[i].y - a[j].y);
            __int128 d_xy_i = (__int128)a[i].x * a[i].x + (__int128)a[j].y * a[j].y;
            __int128 d_xy_j = (__int128)a[j].x * a[j].x + (__int128)a[i].y * a[i].y;

            // Nếu hai điểm cùng lên Ox mà biên M bị vi phạm
            if(d_xx <= M) {
                // Constraint: (i, Ox) AND (j, Ox) -> Forbidden
                // Biến đổi: !(A && B) <=> !A || !B
                // Tương đương: A -> !B và B -> !A
                addImp(g, node(i, 1), neg(node(j, 1))); // i=Ox => j!=Ox
                addImp(g, node(j, 1), neg(node(i, 1))); // j=Ox => i!=Ox
            }
            // Nếu hai điểm cùng lên Oy
            if(d_yy <= M) {
                addImp(g, node(i, 0), neg(node(j, 0))); 
                addImp(g, node(j, 0), neg(node(i, 0)));
            }
            // Nếu điểm i lên Ox, điểm j lên Oy
            if(d_xy_i <= M) {
                addImp(g, node(i, 1), neg(node(j, 0)));
                addImp(g, node(j, 0), neg(node(i, 1)));
            }
            // Nếu điểm j lên Ox, điểm i lên Oy
            if(d_xy_j <= M) {
                addImp(g, node(j, 1), neg(node(i, 0)));
                addImp(g, node(i, 0), neg(node(j, 1)));
            }
        }
    }

    // Solve SCC (Tarjan/Kosaraju)
    // ... (Code SCC đầy đủ) ...
    // Kiểm tra xem có biến nào i và not(i) cùng trong một SCC không
    // return true nếu khả thi
    return true; // Placeholder
}

int main() {
    // Đọc input
    // Binary Search trên câu trả lời
    // In ra giá trị nhỏ nhất tìm được
}

// Pseudocode for the logic
// Note: The provided solutions use 2-SAT, which is the correct optimal approach.
// The 'Simulation' idea mentioned in some scratch thoughts is flawed for general cases
// because it's greedy and doesn't guarantee global optimum.
// However, for N=20, we can do brute force.

// Brute Force for N <= 20 (mentioned in constraints)
#include <bits/stdc++.h>
using namespace std;

int main() {
    int N; cin >> N;
    vector<pair<long long, long long>> pts(N);
    for(int i=0; i<N; i++) cin >> pts[i].first >> pts[i].second;

    long long min_max_dist = LLONG_MAX;

    // Try all 2^N assignments
    for(int mask=0; mask < (1<<N); mask++) {
        vector<long long> ox, oy;
        for(int i=0; i<N; i++) {
            if(mask & (1<<i)) ox.push_back(pts[i].first);
            else oy.push_back(pts[i].second);
        }

        long long current_max = 0;
        // Check distances
        // 1. Points on OX
        if(ox.size() > 1) {
            sort(ox.begin(), ox.end());
            long long d = (ox.back() - ox.front()) * (ox.back() - ox.front());
            current_max = max(current_max, d);
        }
        // 2. Points on OY
        if(oy.size() > 1) {
            sort(oy.begin(), oy.end());
            long long d = (oy.back() - oy.front()) * (oy.back() - oy.front());
            current_max = max(current_max, d);
        }
        // 3. Cross pairs
        for(long long x : ox) {
            for(long long y : oy) {
                long long d = x*x + y*y;
                current_max = max(current_max, d);
            }
        }

        if(current_max < min_max_dist) min_max_dist = current_max;
    }

    cout << min_max_dist << endl;
}