#include <iostream>
#include <stdio.h>
#include <math.h>
#define MAX 1000000000
#define MIN -1000000000
#define PI acos (-1.0)
using namespace std;
double x[50],y[50];
int main() {
	long t,n,j,i;	
	scanf("%d",&t);	
	
	while(t--) {	
		scanf("%d",&n);	
		for(j=0;j<n;j++) {
			scanf("%lf%lf",&x[j],&y[j]);
		}
		double ans = MAX;
		int Time = 30;//细分层数

		int interval = 1000;//细分区间数 

		//from 0 to 90度
		double sum = PI/2;//总区间
		
		double steplen = sum / ((double)interval-2);

		double st = 0;

		double tmp = 0;
		while(Time--) {

			
			for(i=0;i<interval;i++)	{
				
				double getSin=sin(tmp); double getCos=cos(tmp);				
				double down = MAX,left=MAX,up=MIN,right=MIN;				
				for(j=0;j<n;j++)				
				{	
					double nx=x[j]*getCos-y[j]*getSin;
					double ny=y[j]*getCos+x[j]*getSin;
					if(nx<left) left=nx;
					if(nx>right) right=nx;
					if(ny<down) down=ny;
					if(ny>up) up=ny;
				}
				double border=right-left;
				border=(up-down)>border?(up-down):border;

				if(border<ans) {
					ans=border,st=tmp;
				}
				tmp += steplen;
			}
			tmp = st-steplen; //下一层进行该最优值的前后细分
			steplen = ((2*steplen)/(interval-2));
		}
		printf("%.2lf\n",ans * ans);
	}
	return 0;
}

• Re:鸟破题,数据太弱了,N分的错误解法都能混过 (1367) xiefubao 2014-01-26 22:50:52