PKU 3301 Texas Trip

http://poj.org/problem?id=3301
2次元平面上のn個の点を含む最小の正方形の大きさを求めろというような問題。

ある2つの点を回転させる時に角度について3分探索しました。
自信のないアルゴリズム＋EPSがでかいのコンボで1WAだったので、気づけなかったらあきらめてました。

double x[30],y[30];
double rx[30],ry[30];

int n;

double sq(double th){
  rep(k,n){
    double tx=x[k],ty=y[k];
    rx[k]=tx*cos(th)+ty*sin(th);
    ry[k]=tx*(-sin(th))+ty*cos(th);
  }
  return max(*max_element(rx,rx+n)-*min_element(rx,rx+n),
             *max_element(ry,ry+n)-*min_element(ry,ry+n));  
}

void solve(){
  cin>>n;
  rep(i,n)cin>>x[i]>>y[i];
  double ans=sq(0);

  rep(i,n){
    rep(j,i){
      double up=-atan2(y[j]-y[i],x[j]-x[i]);
      double low=up-pi/4;
      while(abs(up-low)>EPS){
        double mid1=(up+low*2)/3;
        double mid2=(up*2+low)/3;
        if(sq(mid1)<sq(mid2))up=mid2;
        else low=mid1;
      }
      ans=min(ans,sq(up));
    }
  }
  printf("%.2f\n",ans*ans);
}

main(){
  int T;
  cin>>T;
  while(T--)solve();
}