PKU 3301 Texas Trip

点が与えられるのでそれらを含む最小の正方形は？

二分探索して角度をがんばって決める。まじめに考えるのが面倒だし制約が小さかったので大量に区間を追加して楽した。
二分探索の回数が足りなくて(30回)誤差死した

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<complex>
using namespace std;
typedef complex<double> Pt;
double x[50];
double y[50];
Pt p[1000];
double PI=acos(-1.0);
pair<double,int> q[100000];
double CAL(double a){
	while(a<0)a+=PI*2;
	while(a>PI*2)a-=PI*2;
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int a;
		scanf("%d",&a);
		for(int i=0;i<a;i++){
			scanf("%lf%lf",x+i,y+i);
		}
		if(a==1){
			printf("0.00\n");
			continue;
		}
		double left=0;
		double right=10000;
		int n=0;
		for(int i=0;i<a;i++){
			for(int j=i+1;j<a;j++)p[n++]=Pt(x[j]-x[i],y[j]-y[i]);
		}
		for(int i=0;i<50;i++){
			double M=(left+right)/2;
			int sz=0;
			for(int j=0;j<n;j++){
				double L=abs(p[j]);
				double th=arg(p[j]);
				//while(th<0)th+=PI/2;
				//while(th>PI/2)th-=PI/2;
				if(M+0.000001>L){
					q[sz++]=make_pair(-99999,+1);
					q[sz++]=make_pair(99999,-1);
					continue;
				}else if(M*sqrt(2.0)-0.0000001<L){
					continue;
				}
				double val=acos(M/L);
			//	printf("%f %f %f\n",M,L,val-th);
				q[sz++]=make_pair(val-th,+1);
				q[sz++]=make_pair(PI/2-val-th,-1);
				q[sz++]=make_pair(PI/2+val-th,+1);
				q[sz++]=make_pair(PI-val-th,-1);
				q[sz++]=make_pair(PI+val-th,+1);
				q[sz++]=make_pair(PI*1.5-val-th,-1);
				q[sz++]=make_pair(PI*1.5+val-th,+1);
				q[sz++]=make_pair(PI*2-val-th,-1);
				q[sz++]=make_pair(val-PI/2-th,+1);
				q[sz++]=make_pair(-val-th,-1);
				q[sz++]=make_pair(val-PI-th,+1);
				q[sz++]=make_pair(-val-PI/2-th,-1);
				q[sz++]=make_pair(val-PI*3/2-th,+1);
				q[sz++]=make_pair(-val-PI-th,-1);
				q[sz++]=make_pair(val-PI*2-th,+1);
				q[sz++]=make_pair(-val-PI*3/2-th,-1);
			}
			std::sort(q,q+sz);
			int count=0;
			bool ok=false;
			for(int j=0;j<sz;j++){
				count+=q[j].second;
				if(count==n)ok=true;
			}
			if(ok)right=M;
			else left=M;
		}
		printf("%.2f\n",left*left);
	}
}