首先题目翻译是有问题的，求的不是矩形而是最小的正方形。
Solution
先考虑一下若正方形的边都只能平行于坐标轴怎么做：找到 \(x,y\) 方向的坐标最值，那么答案就是 \(\max^2\{X_{\max}-X_{\min},Y_{\max}-Y_{\min}\}\)。
接下来，若正方形可以是斜着的，我们只需把坐标轴旋转，然后同样找出旋转后的坐标最值即可。而坐标的变换即为 \((x,y)\rightarrow(x\cos\theta-y\sin\theta,x\sin\theta+y\cos\theta)\)。那么现在的问题就是找到一个合适的旋转角度使得答案最小。
由于此题精度要求较高，所以暴力是行不通的。我看到提交中有一些用了三分，但实际上很明显边长随角度变化不是一个单峰函数，三分能过只是因为数据水了。
那么对于这样的多峰函数，用模拟退火找出最值即可。
Code
#include<bits/stdc++.h>
using namespace std;
#define db double
const int N=33;
const db pi=acos(-1),inf=1e18,eps=1e-15;
int n;
pair<db,db>p[N];
#define fi first
#define se second
#define sqr(x) ((x)*(x))
mt19937 rnd(time(0));
db calc(db a){
db xmn=inf,xmx=-inf,ymn=inf,ymx=-inf;
for(int i=1;i<=n;i++){
db x=p[i].fi,y=p[i].se;
db cx=x*cos(a)-y*sin(a),
cy=x*sin(a)+y*cos(a);
xmn=min(xmn,cx);xmx=max(xmx,cx);
ymn=min(ymn,cy);ymx=max(ymx,cy);
}
return max(xmx-xmn,ymx-ymn);
}
db ans,bk;
void SA(){
double k=bk,t=3000;
while(t>eps){
double kk=k+t*((int)rnd()-INT_MAX);
double now=calc(kk/(db)UINT_MAX*pi);
double dt=now-ans;
if(dt<0)bk=k=kk,ans=now;
else if(exp(-dt/t)*UINT_MAX>rnd())k=kk;
t*=0.996;
}
}
int main(){
int T;scanf("%d",&T);
for(int t=1;t<=T;t++){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lf%lf",&p[i].fi,&p[i].se);
bk=rnd();ans=inf;
for(int i=1;i<=8;i++)SA();
printf("%.2lf\n",ans*ans);
}
return 0;
}