调了半天居然是因为没判断浮点精度误差才\(\colorbox{IndianRed}{\texttt{\color{White}{WA}}}\)了\(3\)个点,其他都没有问题!警钟长鸣……
首先有一个结论:凸多边形的最小外接矩形一定和它的一条边重合。
这个结论,网上几乎找不到完整的证明,目前发现较为清晰的证明是2008年的一篇 一个求解多边形最小面积外接矩形的算法论文(第\(3\)页)。然而这个证明不完整,没有考虑\(4\)个交点的情况中,\(\angle\gamma\)和\(\angle\alpha\)不在对角线划分区域的同一个,如下图:
这种情况仍然能用\(\alpha\)和\(\gamma\)表示出矩形面积,但在这个表达式的取值范围内,面积并不是单调的……总之如果能证出这种情况,整个命题就得证了。大家如果有想法可以发在评论区。
根据这个结论,我们就可以枚举那条和矩形边重合的边\(a\)。进而找到离这条边最远的点,作为矩形的上边界;在垂直于边\(a\)方向上,找左右最远的两点,作为矩形的左、右边界即可。
找左右边界如果和边\(a\)进行比较的话,可以用点积:
\[\vec{a}\cdot\vec{b}=|a||b|\cos{\angle(\vec{a},\vec{b})} \]因此\(\vec{a},\vec{b}\)同向,即\(|\angle(\vec{a},\vec{b})|<\frac{\pi}{2}\)的话,点积\(>0\)。反向则\(<0\),垂直则\(=0\)。
用叉积的话也可以,不过不能和\(a\)做,而是和与\(a\)垂直的向量做(代码用的这种方法)。
与旋转卡壳类似地,随着枚举的边\(a\)的旋转,其他边界顶点仅需从上一次的位置开始移动即可。
找到边界后我们还需要求出四边形的底,高(底就是和边\(a\)重合的那一条边)。高就是\(S\div a\),其中\(S\)是\(\vec{a}\)与上边界形成的平行四边形面积。底的求法详细说一下:
为什么投影长度能转换成点乘呢?因为\(\vec{u}\cdot\vec{a}\)的定义就是\(\vec{u}\)在\(\vec{a}\)上投影的长度再乘\(|\vec{a}|\)嘛,所以再除掉一个\(|\vec{a}|\)就是投影长度了。
为什么要减去呢?因为\(\vec{v}\)的投影长度相对\(\vec{a}\)来说是负数,因此需要变成减号。
点乘公式:\(\vec{a}\cdot\vec{b}=x_a x_b+y_a y_b\)。
注:代码实现中求的是顺时针的凸包,所以\(\vec{a}\)是顺时针的,和图中不一样,自然长度的左减右需要变成右减左。
得到长度之后,四个顶点坐标自然就好求了,具体见代码。
注意精度问题!
点击查看代码
#include<bits/stdc++.h>
#define nxtnode(x) ((x%top)+1)
#define eps 1e-6
#define N 50010
using namespace std;
struct vec{
double x,y;
vec operator+(const vec b){return {x+b.x,y+b.y};}
vec operator-(const vec b){return {x-b.x,y-b.y};}
vec operator*(const double b){return {b*x,b*y};}
double len(){return sqrt(x*x+y*y);}
}a[N],minans[4];//左下,右下,右上,左上
bool cmp(vec a,vec b){return a.x==b.x?a.y<b.y:a.x<b.x;}
inline double cross(vec a,vec b){return a.x*b.y-a.y*b.x;}
inline double dot(vec a,vec b){return a.x*b.x+a.y*b.y;}
int n,st[N],top;
double minn=1e8;
void convex_hull(){//顺时针凸包
sort(a+1,a+1+n,cmp);
st[top=1]=1;
for(int i=2;i<=n;i++){
while(top>1&&cross(a[st[top]]-a[st[top-1]],a[i]-a[st[top]])>-eps)
top--;
st[++top]=i;
}
int tmp=top;
for(int i=n-1;i>=1;i--){
while(top!=tmp&&cross(a[st[top]]-a[st[top-1]],a[i]-a[st[top]])>-eps)
top--;
st[++top]=i;
}
top--;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
convex_hull();
int to=1,le=1,ri;
//to上边界,le左边界,ri右边界
for(int i=1;i<=top;i++){
vec bo=a[st[nxtnode(i)]]-a[st[i]];//枚举重合的边
double len=bo.len();
vec vert={bo.y/len,-bo.x/len};//垂直于bo,长度为1的向量
while(cross(bo,a[st[to]]-a[st[i]])-cross(bo,a[st[nxtnode(to)]]-a[st[i]])>-eps)
to=nxtnode(to);//找上边界
if(i==1) ri=to;//注意必须赋初值为to,否则ri就卡在第1个点不动了
while(cross(a[st[le]]-a[st[i]],vert)-cross(a[st[nxtnode(le)]]-a[st[i]],vert)>-eps)
le=nxtnode(le);//找左边界
while(cross(a[st[ri]]-a[st[i]],vert)-cross(a[st[nxtnode(ri)]]-a[st[i]],vert)<eps)
ri=nxtnode(ri);//找右边界
double lb=dot(a[st[le]]-a[st[i]],bo)/len,rb=dot(a[st[ri]]-a[st[i]],bo)/len;//用点积计算投影长度
double W=cross(a[st[to]]-a[st[i]],bo)/len,L=lb-rb;//高,底
if(W*L<minn){
minn=W*L;
minans[0]=bo*(lb/len)+a[st[i]],minans[1]=bo*(rb/len)+a[st[i]];
minans[2]=minans[1]+vert*W,minans[3]=minans[0]+vert*W;
}
}
cout.setf(ios_base::fixed);
cout.precision(5);
cout<<minn<<"\n";
for(int i=0;i<4;i++)
cout<<minans[i].x<<" "<<minans[i].y<<"\n";
return 0;
}