046：Texas Trip（最小正方形覆盖）

Messj

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

Messj

题目描述

在与Dick一天的旅行之后，Harry在自己SUV的车门上发现了几个奇怪的小孔。而当地的维修店只出售正方形的玻璃纤维修补材料。现在，我们把车门上的小孔当做位于平面上整数坐标的点，问: 至少要一块多大面积的正方形修补材料才能覆盖住所有的小孔？

输入

第一行包含一个整数T (T ≤ 30)，表示有T组测试数据。

对于每一组数据，第一行包含一个整数n (n ≤ 30)，表示有n个小孔。接下来有N行，每行两个整数X和Y，分别表示一个小孔的横坐标和纵坐标。输入数据保证每一个小孔距离原点(0,0)不超过500个单位距离。

输出

对于每一组数据，输出一个两位小数，表示正方形材料的最小面积。

Messj

本题应用了三分算法，参考文章http://blog.csdn.net/littlewhite520/article/details/70144763


给出平面上一些点(坐标),让我们在平面上选择一个正方形能够覆盖这些所有的点,求这个正方形的最小面积。



我们很容易找到一个符合要求的正方形,也就是所有边都平行于坐标轴的正方形,那么我们就只找平行于坐标轴的正方形,我们将每个点都旋转一定的角度,他们的相对位置不变,而正方形却相对于点在旋转,面积在改变,那么就可以找到最小的正方形.

我们只需要考虑最优的旋转角度.

假设旋转的角度为f,初始点的坐标为(x,y)与x轴的夹角为a，距离坐标原点的长度为len,那么x = cos(a)*len,y = sin(a)*len,nx = cos(a+f)*len,ny = sin(a+f)*len

拆开nx = cos(a)*cos(f)*len-sin(a)*sin(f)*len,ny = sin(a)*cos(f)*len+cos(a)*sin(f)*len

也就是说 nx = cos(f)*x-sin(f)*y,ny = sin(f)*x+cos(f)*y;

正方形的边长等于max(rightx-leftx,upy-downy) = max(cos(f)*(x1-x2)-sin(f)*(y1-y2),sin(f)*(x1-x2)+cos(f)*(y1-y2))（x1>x2 &&  y1>y2）

等于 max(sqrt((x1-x2)^2+(y1-y2)^2)sin(f+p1),sqrt((x1-x2)^2+(y1-y2)^2)sin(f+p2))

1. #include<cstdio>
   
2. #include<iostream>
   
3. #include<algorithm>
   
4. #include<cmath>
   
5. #define maxn 31
   
6. #define pi acos(-1.0)
   
7. #define eps 1e-12
   
8. #define inf 0xfffffff
   
9. 
   
10. using namespace std;
    
11. 
    
12. struct E
    
13. {
    
14.         double x,y;
    
15.         E toa(double a)
    
16.         {
    
17.                 E ans;
    
18.                 ans.x=x*cos(a)-y*sin(a);
    
19.                 ans.y=x*sin(a)+y*cos(a);
    
20.                 return ans;
    
21.         }
    
22.        
    
23. }a[maxn];
    
24. int T,n;
    
25. double cal(double x)
    
26. {
    
27.         double minx=inf,miny=inf;
    
28.         double maxx=-inf,maxy=-inf;
    
29.         for(int i=1;i<=n;i++)
    
30.         {
    
31.                 E ans;
    
32.                 ans=a[i].toa(x);
    
33.                 minx=min(minx,ans.x),miny = min(miny,ans.y);
    
34.         maxx = max(maxx,ans.x),maxy = max(maxy,ans.y);       
    
35.         }
    
36.         return max(maxx-minx,maxy-miny);
    
37. }
    
38. int main()
    
39. {
    
40.         scanf("%d",&T);
    
41.         while(T--)
    
42.         {
    
43.                 scanf("%d",&n);
    
44.                 for(int i=1;i<=n;i++)
    
45.                         scanf("%lf%lf",&a[i].x,&a[i].y);
    
46.                 double l=0,r=pi,mid,mmid;
    
47.                 while(l+eps<r)
    
48.                 {
    
49.                         mid=(l+r)/2;
    
50.                         mmid=(mid+r)/2;
    
51.                         if(cal(mid)>cal(mmid))
    
52.                                 l=mid;
    
53.                         else
    
54.                                 r=mmid;
    
55.                 }
    
56.                 double len=cal(l);
    
57.                 printf("%.2lf\n",len*len);
    
58.         }
    
59.         return 0;
    
60. }

复制代码