这题一看就不是计算几何，考虑区间 DP。
设凸多边形的 \(n\) 个顶点依次为 \(P_1,P_2,\cdots,P_n\)。
设 \(f_{i,j}\) 在 \(i < j\) 时表示 \(P_i,P_{i+1},\cdots,P_{j-1},P_j\) 组成的多边形的直径的平方，在 \(i > j\) 时表示 \(P_i,P_{i+1},\cdots,P_n,P_1,\cdots,P_{j-1},P_j\) 组成的多边形的直径的平方。容易得到转移方程：
\[f_{i,j}=\max\{f_{i+1,j},f_{i,j-1},dis^2(P_i,P_j)\}
\]
其中下标均为模 \(n\) 意义下。
答案即为每一对能将多边形分为两个面积为正的部分的点 \((P_i,P_j)\) 中，\(f_{i,j}+f_{j,i}\) 的最小值。其中，\((P_i,P_j)\) 能将多边形分为两个面积为正的部分，当且仅当 \(P_{i-1},P_i,P_j\) 不共线，且 \(P_i,P_{i+1},P_j\) 不共线，使用向量叉积计算即可。
时间复杂度 \(O(n^2)\)。
// Problem: T368391 [GDCPC2023] M-Computational Geometry
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/T368391?contestId=135929
// Memory Limit: 1 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(ll x = (y); x <= (z); ++x)
#define per(x, y, z) for(ll x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;
mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
ll randint(ll L, ll R) {
uniform_int_distribution<ll> dist(L, R);
return dist(rnd);
}
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
const ll N = 5e3 + 5;
ll T, n, x[N], y[N], diam[N][N];
inline ll sq(ll x) {return x * x;}
inline bool line(ll i, ll j, ll k) {
ll v1x = x[i] - x[j], v1y = y[i] - y[j];
ll v2x = x[i] - x[k], v2y = y[i] - y[k];
return v1x * v2y - v2x * v1y == 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
for(cin >> T; T; --T) {
cin >> n;
rep(i, 0, n - 1) cin >> x[i] >> y[i];
auto inc = [&](ll x) {return (x + 1) % n;};
auto dec = [&](ll x) {return (x - 1 + n) % n;};
rep(dt, 1, n - 1) {
rep(L, 0, n - 1) {
ll R = (L + dt) % n;
diam[L][R] = max({diam[inc(L)][R], diam[L][dec(R)], sq(x[L] - x[R]) + sq(y[L] - y[R])});
}
}
ll ans = numeric_limits<ll>::max();
rep(i, 0, n - 1) {
rep(j, 0, n - 1) {
if(!line(dec(i), i, j) && !line(i, inc(i), j)) {
chkmin(ans, diam[i][j] + diam[j][i]);
}
}
}
cout << ans << endl;
}
return 0;
}