poj 3301 Texas Trip (三分，模板题)
题意：
给定二维平面的n个点，要求一个面积最小的正方形，使其能覆盖所有的点。
思路：
先考虑如果水平竖直地放置正方形（边和坐标轴平行）圈住所有点的最小正方形的边长是:
L=max(xmax−xmin,ymax−ymin)
然后考虑如果正方形旋转的话，能圈住所有点的正方形边长是随着角度先减后增的，有凸性，可以三分。。。
但是枚举角度计算正方形的话比较麻烦，可以选择旋转平面上的点，使得正方形仍然是水平竖直放置的，因为这样计算正方形的边长比较方便。 如果把点表示成极坐标形式:
x=r×cosθ,y=r×sinθ,，θ是极角
那么顺时针旋转 α 角度后：
x′=r×cos(θ−α),y=r×sin(θ−α)
化简一下可得：
x′=r×cosθ×cosα+r×sinθ×sinα=x×cosα+y×sinα
y′=r×sinθ×cosα−r×cosθ×sinα=y×cosα−x×sinα
然后就是三分角度了。。。
三分的板子:
1double sanfen(double l,double r)
2{
3 double mid,midmid;
4 while (r-l>eps)
5 {
6 mid = (2*l+r)/3;
7 midmid = (l+2*r)/3;
8 if (cal(mid)>=cal(midmid)) l = mid; //此处为求极小值
9 else r = midmid;
10 }
11 return cal(l);
12
13}
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35/* ***********************************************
36Author :111qqz
37Created Time :2017年10月15日 星期日 00时33分09秒
38File Name :3301.cpp
39************************************************ */
40
41#include <cstdio>
42#include <cstring>
43#include <iostream>
44#include <algorithm>
45#include <vector>
46#include <queue>
47#include <set>
48#include <map>
49#include <string>
50#include <cmath>
51#include <cstdlib>
52#include <ctime>
53#define PB push_back
54#define fst first
55#define sec second
56#define lson l,m,rt<<1
57#define rson m+1,r,rt<<1|1
58#define ms(a,x) memset(a,x,sizeof(a))
59typedef long long LL;
60#define pi pair < int ,int >
61#define MP make_pair
62
63using namespace std;
64const double eps = 1E-8;
65const int dx4[4]={1,0,0,-1};
66const int dy4[4]={0,-1,1,0};
67const int inf = 0x3f3f3f3f;
68const int N=50;
69const double PI = acos(-1.0);
70int n;
71struct point
72{
73 int x,y;
74 void input()
75 {
76 scanf("%d %d",&x,&y);
77 }
78}p[N];
79
80
81double cal( double ang)
82{
83 double minx=1000,miny=1000,maxx=-1000,maxy=-1000;
84 for ( int i = 1 ; i <= n ; i++)
85 {
86 double tmpx = p[i].x * cos(ang) + p[i].y * sin(ang);
87 double tmpy = p[i].y * cos(ang) - p[i].x * sin(ang);
88 minx = min(minx,tmpx);
89 maxx = max(maxx,tmpx);
90 miny = min(miny,tmpy);
91 maxy = max(maxy,tmpy);
92 }
93 return max(maxx-minx,maxy-miny);
94}
95//三分模板
96double sanfen(double l,double r)
97{
98 double mid,midmid;
99 while (r-l>eps)
100 {
101 mid = (2*l+r)/3;
102 midmid = (l+2*r)/3;
103 if (cal(mid)>=cal(midmid)) l = mid; //此处为求极小值
104 else r = midmid;
105 }
106 return cal(l);
107
108}
109
110int main()
111{
112 #ifndef ONLINE_JUDGE
113 freopen("./in.txt","r",stdin);
114 #endif
115// printf("PI:%.12f\n",PI);
116 int T;
117 cin>>T;
118 while (T--)
119 {
120 scanf("%d",&n);
121 for ( int i = 1 ; i <= n ;i++) p[i].input();
122 double ans = sanfen(0,PI);
123 ans*=ans;
124 printf("%.2f\n",ans);
125 }
126 #ifndef ONLINE_JUDGE
127 fclose(stdin);
128 #endif
129 return 0;
130}