poj3301 Texas Trip （三分）

这个三分法对我来说是个比较陌生的东西，就在这里总结一下

二分法适用于单调函数，但是对于单峰函数的解决，就只能用

三分法求解极值了。

对于三分法的话，给一个大神博客的链接：

http://chenjianneng3.blog.163.com/blog/static/128345126201033101044920/

好了，转到正题，这道题的题意是：求出能覆盖一些点的正方形的面积的最小值

题意非常简单，但思维难度有点大

乍一看题，感觉无从下手，就找了几个例子来试验，结果也没研究出什么名堂，就

只好去翻题解，看了题解，感觉恍然大悟，自己试验的那几个例子，都暗藏着这个

玄机。

首先，需要一个东西：对于平面上任意的一个点集，正方形边长等于max（两点之间的最大横坐标距离，两点之间的最大纵坐标距离）时

，该正方必能覆盖这个点集。

对于上面那个玩意儿，应该是比较显然的，然后呢，也可以看出这样虽然可以找到一个满足覆盖点集的正方形，但是并不一定能够保证面

积最小。好，精彩的地方来了：我们可以旋转坐标系，得到许多不同的正方形，面积最小的正方形必在其中。（这个也比较显然，根据贪

心的思维，自然是越多点在正方形的边上越好，所以面积最小的正方形一定有至少两个点在它的边上）

那么旋转坐标系后，对于每个点，它的坐标将有这样的变化

（下面证明不充分，只证明了旋转前旋转后都在一象限的情况，后面的强行同理吧）

假设坐标轴旋转的角度为a，点的坐标(x,y)，点关于x轴的夹角为b

令t=sqrt(x*x+y*y)

那么新的点的坐标的表达式就是(t*cos(a+b),t*sin(a+b))

根据三角函数的公式，及cos b=x/t , sin b=y/t，展开可得：

坐标为：(x*cos a-y*sin a ,x*sin a+y*cos a);

即 x'=x*cos a-y*sin a , y'=x*sin a+y*cos a

网上的好多篇文章都是推到了这一步，然后就什么分析易得，正方形的

面积是一个下凸包啊，甚至直接上代码，表示懵比，这让我这种渣渣这么办。。。

根据上面推出来的东西，正方形面积的表达式应该是

max( xmax - xmin ,ymax - ymin )^2

然后展开化标，再进行一堆三角变换，分情况讨论，就能得到这是个下凸包了，不赘述

然后就是三分了，三分坐标系的旋转角度a （你得到的面积表达式的自变量）

代码：（精度要求好高的说，就因为精度wa了好多次）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>

const int MAXN=40;
const double pi=acos(-1.0);
const double esp=1e-12;
const double inf=1000;
using namespace std;
struct node{double x,y;}p[MAXN];
int T,N;

double lenth(double a){//!求坐标系旋转a时的正方形边长
    double tx,ty,x1=-inf,y1=-inf,x2=inf,y2=inf;
    for(int i=1;i<=N;i++)
    {
        tx=p[i].x*cos(a)-p[i].y*sin(a);
        ty=p[i].x*sin(a)+p[i].y*cos(a);
        x1=max(tx,x1);  y1=max(ty,y1);
        x2=min(tx,x2);  y2=min(ty,y2);
    }
    return max(x1-x2,y1-y2);
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&N);
        for(int i=1;i<=N;i++)
        {
            scanf("%lf",&p[i].x);
            scanf("%lf",&p[i].y);
        }
        double l=0.0,r=pi,mid,midmid,ans=0.0;
        while(r-l>=esp)
        {
            mid=(l+r)*0.5;
            midmid=(mid+r)*0.5;
            ans=lenth(mid);
            if(ans<=lenth(midmid))
                r=midmid;
            else l=mid;
        }
        printf("%.2lf\n",ans*ans);
    }
    return 0;
}