[POJ3301]Texas Trip

原出处：http://blog.csdn.net/qq_37816449/article/details/75142734

After a day trip with his friend Dick, Harry noticed a strange pattern of tiny holes in the door of his SUV. The local American Tire store sells fiberglass patching material only in square sheets. What is the smallest patch that Harry needs to fix his door?

Assume that the holes are points on the integer lattice in the plane. Your job is to find the area of the smallest square that will cover all the holes.

Input

The first line of input contains a single integer T expressed in decimal with no leading zeroes, denoting the number of test cases to follow. The subsequent lines of input describe the test cases.

Each test case begins with a single line, containing a single integer n expressed in decimal with no leading zeroes, the number of points to follow; each of the following n lines contains two integers x and y, both expressed in decimal with no leading zeroes, giving the coordinates of one of your points.

You are guaranteed that T ≤ 30 and that no data set contains more than 30 points. All points in each data set will be no more than 500 units away from (0,0).

Output

Print, on a single line with two decimal places of precision, the area of the smallest square containing all of your points.

Sample Input

2
4
-1 -1
1 -1
1 1
-1 1
4
10 1
10 -1
-10 1
-10 -1

Sample Output

4.00
242.00

题意：给出n个点，求能将所有点覆盖的正方形的最小面积

题解：

对于平面上任意的一个点集，正方形边长等于max（两点之间的最大横坐标距离，两点之间的最大纵坐标距离）时，该正方必能覆盖这个点集。

但这样找到的满足覆盖点集的正方形，并不一定能够保证面积最小。于是我们可以旋转坐标系，得到许多不同的正方形，面积最小的正方形必在其中。

这个也比较显然，根据贪心的思维，自然是越多点在正方形的边上越好，所以面积最小的正方形一定有至少两个点在它的边上

三分角度求解，旋转角度为[ 0, π ]。

对于点P( x, y ), 其距原点的距离L=sqrt( x*x+y*y ), 
与原点的连线和x轴形成的角度为α
坐标也可写为( L*cos(α), L*sin(α) )
若点绕原点旋转Δ度, 那么
x' = L*cos(α+Δ) = L*cos(α)*cos(Δ) - L*sin(α)*sin(Δ) = x*cos(Δ)-y*sin(Δ)
y' = L*sin(α+Δ) = L*sin(α)*cos(Δ) + L*cos(α)*sin(Δ) = x*sin(Δ)+y*cos(Δ)
所以点P'( x', y' ) = ( x*cos(Δ)-y*sin(Δ), x*sin(Δ)+y*cos(Δ) )

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const double INF=1e50;
const double eps=1e-9;
const double PI=acos(-1.0); 
const int N=35;
int T, n;
struct node{ double x, y; }p[N];

double length( double delta ) {
	double maxx=-INF, minx=INF;
	double maxy=-INF, miny=INF;
	for( int i=1; i<=n; i++ ) {
		double xx=p[i].x*cos(delta)-p[i].y*sin(delta);
		double yy=p[i].x*sin(delta)+p[i].y*cos(delta);
		maxx=max( maxx, xx ); minx=min( minx, xx );
		maxy=max( maxy, yy ); miny=min( miny, yy );
	}
	return max( maxx-minx, maxy-miny );
}

int main() {
	for( scanf( "%d", &T ); T; T-- ) {
		scanf( "%d", &n );
		for( int i=1; i<=n; i++ )
			scanf( "%lf%lf", &p[i].x, &p[i].y );
		double down=0, up=PI, Ll, Lr;
		while( up-down>eps ) {
			double midl=(down+up)/2;
			double midr=(midl+up)/2;
			Ll=length( midl );
			Lr=length( midr );
			if( Ll<Lr ) up=midr;
			else down=midl;
		}
		printf( "%.2lf\n", Ll*Ll );
	}
	return 0;
}