poj 3301

题意：给出一些点的坐标，求一个最小的正方形来覆盖所有的点

用三分枚举转角即可，坐标转换公式： x’ = x * cosa - y * sina; y’ = y * cosa + x * sina;

View Code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 
 7 #define N 60
 8 #define inf 100000000
 9 #define eps 1e-8
10 double const pi=acos(-1.0);
11 struct node
12 {
13     double x,y;
14 }p[N],tp[N];
15 int n;
16 node cal(node a,double key)
17 {
18     node temp;
19     temp.x = a.x * cos(key) - a.y * sin(key);
20     temp.y = a.y * cos(key) + a.x * sin(key);
21     return temp;
22 }
23 double ca(double key)
24 {
25     double minx,miny,maxx,maxy;
26     minx = miny = inf;
27     maxx = maxy = -inf;
28     for(int i = 0; i < n; i++)
29     {
30         tp[i] = cal(p[i],key);
31         minx = min(minx,tp[i].x);
32         miny = min(miny,tp[i].y);
33         maxx = max(maxx,tp[i].x);
34         maxy = max(maxy,tp[i].y);
35     }
36     double tx = maxx - minx;
37     double ty = maxy - miny;
38     return max(tx * tx,ty * ty);
39 }
40 int main()
41 {
42     int cas;
43     //freopen("data.txt","r",stdin);
44     scanf("%d",&cas);
45     while(cas--)
46     {
47         scanf("%d",&n);
48         for(int i=0; i<n; i++)
49         {
50             scanf("%lf%lf",&p[i].x,&p[i].y);
51         }
52         double l = 0.0;
53         double r = pi;
54         double lmid,rmid;
55         while(fabs(r - l) > eps)
56         {
57             lmid = (l * 2.0 + r) / 3.0;
58             rmid = (l + r * 2.0) / 3.0;
59             if(ca(lmid) > ca(rmid))  l = lmid;
60             else r = rmid;
61         }
62         printf("%.2lf\n",ca(l));
63     }
64     return 0;
65 }