//http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2301597#2
// ???????????????????§£?????????
// ?§£??????dp??????????????§???????£?10  ??????????????° 15 ???
// O(n^2)??§?§£???????????§??????????????????1000??\?????§?????????10^9??\????????¶?????§??????????????¨?§£????????????????????????
//????????????????°????????????£????????°??????????????????????????????????????£??????

#include<iostream>
#include<functional>
#include<vector>
#include<algorithm>
#include<queue>

#define MAX 100000000000;

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int , int> P;
typedef vector<P> vP;
typedef vector<vi> vvi;

vl XY[20001];
vl YX[20001];
ll answer = MAX;

ll solve(int xs, int xe,int ys,int ye) {
	if (xe - xs > ye - ys) {
		int num = 0;
		for (int i = ys; i < ye; i++) {
			num += distance(lower_bound(YX[i].begin(), YX[i].end(), xs), upper_bound(YX[i].begin(), YX[i].end(), xe - 1));
			if (num > 1)break;
		}
		if (num <= 1)return MAX;
		int m = (xe + xs) / 2;
		ll s1 = solve(xs, m, ys, ye);
		ll s2 = solve(m, xe, ys, ye);
		ll s = min(s1, s2);
		ll ans = min(answer,s);
		for (ll i = m; i < min((ll)xe, m + ans); i++) {
			for (ll j = max((ll)xs, i - ans); j < m; j++) {
				if (XY[i].empty() || XY[j].empty())continue;
				auto it1 = lower_bound(XY[i].begin(), XY[i].end(), ys);
				auto it2 = lower_bound(XY[j].begin(), XY[j].end(), ys);
				if (it1 == XY[i].end() || it2 == XY[j].end())continue;
				while (it2 != XY[j].end() && (*it2)<ye) {
					while ((*it1) < (*it2)) {
						++it1;
						if (it1 == XY[i].end()||(*it1)>=ye)break;
					}
					if (it1 == XY[i].end()||(*it1)>=ye)break;
					ans = min(ans,
						(i - j)*(i - j) + ((*it1) - (*it2))*((*it1) - (*it2)));
					++it2;
				}
				it1 = lower_bound(XY[i].begin(), XY[i].end(), ys);
				it2 = lower_bound(XY[j].begin(), XY[j].end(), ys);
				if (it1 == XY[i].end() || it2 == XY[j].end())continue;
				while (it1 != XY[i].end()&& (*it1)<ye) {
					while ((*it1) > (*it2)) {
						++it2;
						if (it2 == XY[j].end()|| (*it2) >= ye)break;
					}
					if (it2 == XY[j].end()|| (*it2) >= ye)break;
					ans = min(ans,
						(i - j)*(i - j) + ((*it1) - (*it2))*((*it1) - (*it2)));
					++it1;
				}
			}
		}
	//cout << xs << " " << xe << " " << ys << " " << ye << " " << ans<< endl;
		answer = min(answer, ans);
		return ans;
	}
	else {
		int num = 0;
		for (int i = xs; i < xe; i++) {
			num += distance(lower_bound(XY[i].begin(), XY[i].end(), ys), upper_bound(XY[i].begin(), XY[i].end(), ye - 1));
			if (num > 1)break;
		}
		if (num <= 1)return MAX;
		int m = (ye + ys) / 2;
		ll s1 = solve(xs, xe, ys, m);
		ll s2 = solve(xs, xe, m, ye);
		ll s = min(s1, s2);
		ll ans = min(answer,s);
		for (ll i = m; i < min((ll)ye, m + ans); i++) {
			for (ll j = max((ll)ys, i - ans); j < m; j++) {
				if (YX[i].empty() || YX[j].empty())continue;
				auto it1 = lower_bound(YX[i].begin(), YX[i].end(), xs);
				auto it2 = lower_bound(YX[j].begin(), YX[j].end(), xs);
				if (it1 == YX[i].end() || it2 == YX[j].end())continue;
				while (it2 != YX[j].end() && (*it2)<xe) {
					while ((*it1) < (*it2)) {
						++it1;
						if (it1 == YX[i].end()||(*it1)>=xe)break;
					}
					if (it1 == YX[i].end()||(*it1)>=xe)break;
					ans = min(ans,
						(i - j)*(i - j) + ((*it1) - (*it2))*((*it1) - (*it2)));
					++it2;
				}
				it1 = lower_bound(YX[i].begin(), YX[i].end(), xs);
				it2 = lower_bound(YX[j].begin(), YX[j].end(), xs);
				if (it1 == YX[i].end() || it2 == YX[j].end())continue;
				while (it1 != YX[i].end() && (*it2)<xe) {
					while ((*it1) > (*it2)) {
						++it2;
						if (it2 == YX[j].end() || (*it2) >= xe)break;
					}
					if (it2 == YX[j].end() || (*it2) >= xe)break;
					ans = min(ans,
						(i - j)*(i - j) + ((*it1) - (*it2))*((*it1) - (*it2)));
					++it1;
				}
			}
		}
	//cout << xs << " " << xe << " " << ys << " " << ye << " " << ans<< endl;
		answer = min(ans, answer);
		return ans;
	}
}
int main(){
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		x += 10000;
		y += 10000;
		XY[x].push_back(y);
		YX[y].push_back(x);
	}
	for (int i = 0; i < 20001; i++) {
		sort(XY[i].begin(), XY[i].end());
		sort(YX[i].begin(), YX[i].end());
	}
	cout << solve(0, 20001, 0, 20001) << endl;
	return 0;
}

Measured memory_bytes: 18536