poj3301 Texas Trip(3분구 극치)

Texas Trip
Time Limit: 1000MS
 
Memory Limit: 65536K
Total Submissions: 3233
 
Accepted: 948
Description
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

Source
Waterloo Local Contest, 2007.7.14
먼저 회전하는 각도는 0도에서 180도만 있으면 되고 180도를 초과하면 앞의 것과 같다.좌표축이 회전하면 그래프의 좌표는 다음과 같이 변환됩니다.
X’ = x * cosa - y * sina;
y’ = y * cosa + x * sina;
좌표축이 원점을 돌고 시계 반대 방향으로 회전하는 각도는 도형이 원점을 돌고 시계 반대 방향으로 회전하는 각도에 해당한다. 각도는 마이너스를 취하고 좌표의 전환 공식은 구하기 쉬우므로 좌표를 그려 연구하면 나온다.
문제는 가장 작은 정사각형을 요구하는 것이다. 만약에 이 정사각형의 변이 각각 좌표축과 평행이라고 가정하면 정사각형은 일정한 각도를 회전하지 않는다는 것이다. 그러면 우리는 맨 위, 맨 아래, 가장 왼쪽, 가장 오른쪽 점을 고려하면 된다.정사각형이 일정한 각도를 회전하면 d는 우리도 가장 가장자리에 있는 점의 거리차만 고려하면 된다. 그러므로 이 문제는 회전 각도를 매거진 방법으로 풀 수 있지만 보폭이 긴 선택에 주의하여 정밀도를 확보해야 한다.
yi-yj는 회전 후의 좌표의 y방향의 최대 길이에 해당하고,xi-xj는 회전 후의 좌표의 x방향의 최대 길이에 해당하며, 둘 중 가장 큰, 매거변의 길이를 취하여 면적이 가장 작은 정사각형을 찾아낸다.
회전 각도가 d라고 가정하면 각 두 점의 회전 각도가 d인 직선 거리에 대한 최대치를 일일이 열거하면 모든 점을 덮어쓰고 수직과 평행 좌표축 두 방향에서 이러한 거리는 각각 다음과 같다.
   dis1 = fabs(cos(d) * (y[i] - y[j]) - sin(d) * (x[i] - x[j]))
   dis2 = fabs(sin(d) * (y[i] - y[j]) + cos(d) * (x[i] - x[j]))
물론dis1과dis2의 크기가 반드시 일치하지 않습니다. 도형이 모든 점을 덮어쓰는 정사각형임을 보증하기 때문에 우리는 비교적 큰 것을 가장자리로 선택합니다.

#include<iostream>
#include<cstdio>
#include<cmath>
#define eps 1e-12
using namespace std;
struct point
{
    double x,y;
};
point data[35];
int n;
int sgn(double a)
{
    return (a>eps)-(a<-eps);
}
double dist1(double g)
{
    int i,j;double m=0,k;
    for(i=0;i<n-1;i++)
    for(j=i+1;j<n;j++)
    {
      k=fabs((data[i].y-data[j].y)*cos(g)-(data[i].x-data[j].x)*sin(g));
      if(k>m)
      m=k;
    }
    return m;
}
double dist2(double g)
{
    int i,j;double m=0,k;
    for(i=0;i<n-1;i++)
    for(j=i+1;j<n;j++)
    {
      k=fabs((data[i].y-data[j].y)*sin(g)+(data[i].x-data[j].x)*cos(g));
      if(k>m)
      m=k;
    }
    return m;
}
double ping(double a,double b)
{
    return a>b?a*a:b*b;
}
void work()
{
    double t1,t2,l,r,mid1,mid2;
    l=0;r=acos(-1.0);
    do
    {
       mid1=(l+r)*0.5;
       mid2=(mid1+r)*0.5;
       t1=ping(dist1(mid1),dist2(mid1));
       t2=ping(dist1(mid2),dist2(mid2));
       if(t1<t2)
       r=mid2;
       else
       l=mid1;
    }
    while(sgn(r-l)>0);
    printf("%.2lf
",t1);
}
int main()
{
    int t,i;
    double ff;
    scanf("%d",&t);
     while(t--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
        scanf("%lf%lf",&data[i].x,&data[i].y);
        work();
    }

    return 0;
}