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);
}
/* ***********************************************
Author :111qqz
Created Time :2017年10月15日 星期日 00时33分09秒
File Name :3301.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=50;
7const double PI = acos(-1.0);
8int n;
9struct point
10{
11 int x,y;
12 void input()
13 {
14 scanf("%d %d",&x,&y);
15 }
16}p[N];
1double cal( double ang)
2{
3 double minx=1000,miny=1000,maxx=-1000,maxy=-1000;
4 for ( int i = 1 ; i <= n ; i++)
5 {
6 double tmpx = p[i].x * cos(ang) + p[i].y * sin(ang);
7 double tmpy = p[i].y * cos(ang) - p[i].x * sin(ang);
8 minx = min(minx,tmpx);
9 maxx = max(maxx,tmpx);
10 miny = min(miny,tmpy);
11 maxy = max(maxy,tmpy);
12 }
13 return max(maxx-minx,maxy-miny);
14}
15//三分模板
16double sanfen(double l,double r)
17{
18 double mid,midmid;
19 while (r-l>eps)
20 {
21 mid = (2*l+r)/3;
22 midmid = (l+2*r)/3;
23 if (cal(mid)>=cal(midmid)) l = mid; //此处为求极小值
24 else r = midmid;
25 }
26 return cal(l);
}
1int main()
2{
3 #ifndef ONLINE_JUDGE
4 freopen("./in.txt","r",stdin);
5 #endif
6// printf("PI:%.12f\n",PI);
7 int T;
8 cin>>T;
9 while (T--)
10 {
11 scanf("%d",&n);
12 for ( int i = 1 ; i <= n ;i++) p[i].input();
13 double ans = sanfen(0,PI);
14 ans*=ans;
15 printf("%.2f\n",ans);
16 }
17 #ifndef ONLINE_JUDGE
18 fclose(stdin);
19 #endif
20 return 0;
21}