Problem 1185. -- [HNOI2007]最小矩形覆盖
http://hzwer.com/5805.html
覆盖问题和不是凸包上的点没关系，先做凸包。根据贪心的思想，这个覆盖了所有点的矩形肯定至少有一条边与凸包上的边重合，那么我们枚举凸包上的每一条边，对于这个已经确定了一条边的矩形，不难确定其他三个边。注意到已知当前直线的向量，就可以求出两侧和对面的向量，而这三个向量随着枚举的边的移动是单调的，所以就可以用旋转卡壳来卡住剩下的三条边。
但是旋转卡壳时的初值会出问题，如果按照逆时针的顺序求出剩下的三条边的时候，要想通过向量直接卡第三条边的方向是不行的，因为它和第一条边正好是反过来的，所以对于同一条边来说，与第一条边的夹角和第三条边的夹角一个是顺时针另一个是逆时针。这肯定会出问题。所以要预处理出枚举的第一条边，算出三个边的位置，作为旋转卡壳的初值。可以证明，在凸包上的其他边每次旋转肯定不会超过180°，所以不会发生类似的bug。
枚举凸包上的边
用旋转卡壳在凸包上找矩形另外三点。。。
然后我们自然就是对于每一条边考虑一下:首先找到距离这条边最远的点.然后从这个点到这条边做一条垂线段,用这条垂线段上下平移来得到两个边界.
于是我用旋转卡壳找最远的点,然后对于两边分别三分.
效率好像还不低.
http://www.wenku1.com/view/FE4448EBFE4F0551.html
Graham-Scan算法：
Gift-Wrapping算法无论从理解还是从实现上来说，它都是十分简单的。但由于它的复杂度并不理想，我们无法利用它来求解大
规模的凸包问题。因而，我们将介绍一种高效的计算凸包的算法――Graham-Scan。
Graham-Scan算法主要可分成两部分：
1） 同Gift-Wrapping一样，需要先找出一个起始点。将这个点作为原点，进行夹角排序。
2） 先将起始点压入堆栈H中，再按照已经排好的顺序对每一个点进行扫描，同时维护堆栈H。这个堆栈表示的是到目前为止，所有
已经扫描过的点对应的凸包。每当扫描一个点p的时候：
a) 如果堆栈的元素少2个或者堆栈顶端的两个点与p构成左转关系，则将p压入堆栈中。
b) 否则，栈顶元素出栈并继续进行a的判断。
当所有点都扫描完后，堆栈H即为我们要求的凸包。
图二：Graham-Scan算法的扫描过程（堆栈H储存的即实线连接起来的点）
分析Graham-Scan的复杂度：第一步中找出起点并进行极角排序的复杂度是 O（n log n）。第二步中每一个点仅会被扫描
一次并相应维护一次堆栈H 。而维护堆栈过程中每次访问堆栈H中的点，要么这个点被删除，要么就停止堆栈的维护，所以所有堆栈维
护加起来最多只访问了2n次。故这部分的复杂度是O（n）。综合起来，Graham-Scan算法的时间复杂度是O（n log n）的。
算法分析：
现在考虑这道题目，题目要我们求出一个最小面积的矩形能够覆盖给定的所有点。易知矩形覆盖所有点当且仅当它覆盖这些点的凸
包。故而，问题可以转化为对于一个凸包，求出一个面积最小的矩形来覆盖它。
那么这个覆盖凸包的最小矩形有什么性质呢？
首先，这个矩形的四条边上必然都有凸包的顶点。这个很容易想清楚，如果矩形的某条边没有碰上凸包的顶点，那么我们一定能把
这条边向里压，从而得到一个更小的满足条件的矩形。
其次，这个矩形至少有一条边与凸包上的一边重合。这个性质不容易直观地想清楚，需要书面证明一下。由于完整的证明需要分成
很多情况来讨论，比较繁琐，所以这里仅选取其中的一种情况来证明，其他情况可以类似地进行证明。
利用反证法，我们假设覆盖凸包的最小矩形所有边都没有和凸包的边有重合，也就是说，最小矩形的每条边上仅有一个凸包的顶
点。如图三所示，矩形ABCD是覆盖凸包的最小矩形，M、N、P、Q为凸包在矩形四条边上的顶点。我们分别作MM’⊥ CD,NN’⊥ AD。则
矩形ABCD的面积S = MP×Cos(∠PMM’)×NQ×Cos(∠QNN’)。我们将矩形旋转X度（顺时针为正，逆时针为负），仍使矩形覆盖凸包且
M、N、P、Q分别在它的四边上。则此时新矩形的面积S = MP×Cos(∠PMM’+ X)×NQ×Cos(∠QNN’- X) 。我们仅需考虑Cos(∠PMM’+
X)×Cos(∠QNN’- X)的单调性。
Cos(∠PMM’+ X)×Cos(∠QNN’- X)
= 1/2[Cos(∠PMM’+ X + ∠QNN’- X) + Cos(∠PMM’+ X - ∠QNN’+ X)]
= 1/2[Cos(∠PMM’+ ∠QNN’) + Cos(∠PMM’- ∠QNN’+ 2X)]
∵0≤∠PMM’＜ π/2 , 0≤∠QNN’＜ π/2
∴-π/2 ＜∠PMM’- ∠QNN’＜ π/2
∴Cos(∠PMM’- ∠QNN’)不可能取到最小值
∴x在0左边的一个区间中f(x) = Cos(∠PMM’- ∠QNN’+ 2X)递增，或x在0右边一个区间中f(x) = Cos(∠PMM’- ∠QNN’+ 2X)递
减。
因而，对于这样的矩形，我们总可以顺时针或逆时针旋转一个小角度，从而获得一个更小的矩形，这与假设矛盾。故最小矩形至少
有一条边与凸包一边重合。
了解到最小矩形所具有的这两个性质后，我们就能够很容易的想到一种算法，枚举凸包上哪条边与矩形的边重合，再找出在这
条直线投影的正负方向上最远的和到直线距离最远的三点，从而确定和计算出矩形的面积，最后选取最小值，即为覆盖凸包的最小矩形
的面积。
我们用最朴素的方法去实现它，枚举每条边后再把剩余的点都扫描一遍，来找出另外三点，计算出矩形的面积。这样做时间复杂
度是O（n2）得。就本题来说已经可以接受了。但如果规模再大一点，怎么办呢？我们能不能做得更好呢？
答案是能！我们还有一个很重要的信息没有利用到，对凸包上任意一条边，依次计算出凸包顶点到它的距离或投影距离，构成的
序列总是一个先增再降的。同时，注意到如果逆时针顺序枚举重合的边时，每次找出来的另外三点也总是在向逆时针方向移动。
由此，我们就得到了一个更加高效的算法。枚举过程中，逆时针旋转到下一条边后不需要再重新扫描所有点，只要分别从上一条
边确定的三点出发，向后比较，找到最大值，来更新这三个点即可。
在枚举过程中，三个点的指针都只会对每个顶点访问一次，所以这个过程的平摊复杂度是O（n）的。结合前面计算凸包的过程，在O
（n log n）的时间内我们就能够圆满地解决这题了。
了解到最小矩形所具有的这两个性质后，我们就能够很容易的想到一种算法，枚举凸包上哪条边与矩形的边重合，再找出在这
条直线投影的正负方向上最远的和到直线距离最远的三点，从而确定和计算出矩形的面积，最后选取最小值，即为覆盖凸包的最小矩形
的面积。
http://hzwer.com/5805.html
struct P{
double x,y;
P(){}
P(double _x,double _y):x(_x),y(_y){}
friend bool operator<(P a,P b){
return fabs(a.y-b.y)<eps?a.x<b.x:a.y<b.y;
}
friend bool operator==(P a,P b){
return fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps;
}
friend bool operator!=(P a,P b){
return !(a==b);
}
friend P operator+(P a,P b){
return P(a.x+b.x,a.y+b.y);
}
friend P operator-(P a,P b){
return P(a.x-b.x,a.y-b.y);
}
friend double operator*(P a,P b){
return a.x*b.y-a.y*b.x;
}
friend P operator*(P a,double b){
return P(a.x*b,a.y*b);
}
friend double operator/(P a,P b){
return a.x*b.x+a.y*b.y;
}
friend double dis(P a){
return sqrt(a.x*a.x+a.y*a.y);
}
}p[50005],q[50005],t[5];
bool cmp(P a,P b)
{
double t=(a-p[1])*(b-p[1]);
if(fabs(t)<eps)return dis(p[1]-a)-dis(p[1]-b)<0;
return t>0;
}
void graham()
{
for(int i=2;i<=n;i++)
if(p[i]<p[1])
swap(p[i],p[1]);
sort(p+2,p+n+1,cmp);
q[++top]=p[1];
for(int i=2;i<=n;i++)
{
while(top>1&&(q[top]-q[top-1])*(p[i]-q[top])<eps)top--;
q[++top]=p[i];
}
q[0]=q[top];
}
void RC()
{
int l=1,r=1,p=1;
double L,R,D,H;
for(int i=0;i<top;i++)
{
D=dis(q[i]-q[i+1]);
while((q[i+1]-q[i])*(q[p+1]-q[i])-(q[i+1]-q[i])*(q[p]-q[i])>-eps)p=(p+1)%top;
while((q[i+1]-q[i])/(q[r+1]-q[i])-(q[i+1]-q[i])/(q[r]-q[i])>-eps)r=(r+1)%top;
if(i==0)l=r;
while((q[i+1]-q[i])/(q[l+1]-q[i])-(q[i+1]-q[i])/(q[l]-q[i])<eps)l=(l+1)%top;
L=(q[i+1]-q[i])/(q[l]-q[i])/D,R=(q[i+1]-q[i])/(q[r]-q[i])/D;
H=(q[i+1]-q[i])*(q[p]-q[i])/D;
if(H<0)H=-H;
double tmp=(R-L)*H;
if(tmp<ans)
{
ans=tmp;
t[0]=q[i]+(q[i+1]-q[i])*(R/D);
t[1]=t[0]+(q[r]-t[0])*(H/dis(t[0]-q[r]));
t[2]=t[1]-(t[0]-q[i])*((R-L)/dis(q[i]-t[0]));
t[3]=t[2]-(t[1]-t[0]);
}
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
graham();
RC();
printf("%.5lf\n",ans);
int fir=0;
for(int i=1;i<=3;i++)
if(t[i]<t[fir])
fir=i;
for(int i=0;i<=3;i++)
printf("%.5lf %.5lf\n",t[(i+fir)%4].x,t[(i+fir)%4].y);
return 0;
}
Read full article from Problem 1185. -- [HNOI2007]最小矩形覆盖