洛谷 P3187 [HNOI2007]最小矩形覆盖 题解【凸包】【旋转卡壳】

点击量：236

    感觉对旋转卡壳的理解又多了一点点……不过这个题莫名卡精度啊

目录

题目描述

给定一些点的坐标，要求求能够覆盖所有点的最小面积的矩形，输出所求矩形的面积和四个顶点坐标

输入输出格式

输入格式：

第一行为一个整数\(n(3\le n\le 50000)\)，从第\(2\)至第\(n+1\)行每行有两个浮点数，表示一个顶点的\(x\)和\(y\)坐标，不用科学计数法

输出格式：

第一行为一个浮点数，表示所求矩形的面积（精确到小数点后\(5\)位），接下来\(4\)行每行表示一个顶点坐标，要求第一行为\(y\)坐标最小的顶点，其后按逆时针输出顶点坐标.如果用相同\(y\)坐标，先输出最小\(x\)坐标的顶点

输入输出样例

输入样例#1：

6 1.0 3.00000
1 4.00000
2.0000 1
3 0.0000
3.00000 6
6.0 3.0

输出样例#1：

18.00000
3.00000 0.00000
6.00000 3.00000
3.00000 6.00000
0.00000 3.00000

题解：

    可以拿来当以后旋转卡壳的板子，就像洛谷 P2042 [NOI2005]维护数列作为平衡树板子一样？

\[flag\times 1\]

    需要先求出这个点集的凸包。因为如果一个矩形覆盖了整个凸包，那么凸包内的点也一定全部被覆盖到了。

    通过对计算几何和凸多边形的了解，最优解中，凸包一定有一条边在矩形上，否则可以通过旋转使得面积减小。这非常符合我们旋转卡壳的思想，可以枚举边，找边的对踵点，然后再进行其他操作。

    那么当凸包的一对平行切线被找到后，我们需要构造与这两条切线垂直的令一对平行切线。由于第一对是固定的，凸包也是固定的，所以要求的这一对切线是唯一的。如果把整个图形随第一对切线旋转到水平位置，那么我们要找的就是最左边点位置的切线和最右边点位置的切线。

    因此还要类似旋转卡壳维护最下边这条边对应的左端点和右端点。考虑它们的性质。

    如果认为每一个点所代表的向量是以它为起点，以它顺时针方向的点为终点构成的，例如\(\vec{a}=\overrightarrow{AB}\)。那么针对\(\vec{a}\)这条边而言，\(vec{c}\)是左边第一条与它数量积（点积）为正的边，同时\(\vec{d}\)是右边第一条与它数量积为负的边。而\(AB\)又在不断逆时针旋转，这时\(C,D\)也在逆时针旋转，就可以用two-pointer思维，\(C,D\)和\(AB\)的对踵点在整个过程中只会被更新\(O(n)\)次，保证了时间复杂度。

    不过要注意，\(D\)点和\(AB\)的对踵点（称作\(E\)）的枚举起点可以是\(A\)或\(B\)，因为顺着找下去，它们的结果都是单调的，然而\(C\)点的枚举起点需要在\(D\)点后面，因为我们要找左边第一个与\(\overrightarrow{AB}\)数量积为正的边，而\(\overrightarrow{BD}\)也满足，就不好确定我们想要的点在哪里。但是由于\(\overrightarrow{BD}\)是最后一段满足条件的向量，因此从\(D\)后面枚举就没问题了。

    最后用线段相交的知识求出四对边的交点即可。（线段相交填坑后会加上链接）

    bzoj上这个题有spj，精度难度会略有下降。

Code：

#include<cstdio>
#include<algorithm>
#include<cmath>
#define db double
#define eps 1e-8
struct vct
{
    db x,y;
    vct(db x,db y)
    {
        this->x=x;
        this->y=y;
    }
    vct(){}
    db dis()
    {return sqrt(x*x+y*y);}
    vct times(db u)
    {return vct(x*u,y*u);}
    friend bool operator <(vct a,vct b)
    {
        if(fabs(a.x-b.x)>eps)
            return a.x<b.x;
        return a.y<b.y;
    }
    friend vct operator +(vct a,vct b)
    {return vct(a.x+b.x,a.y+b.y);}
    friend vct operator -(vct a,vct b)
    {return vct(a.x-b.x,a.y-b.y);}
    friend db operator *(vct a,vct b)
    {return a.x*b.y-a.y*b.x;}
    friend db operator %(vct a,vct b)//点积
    {return a.x*b.x+a.y*b.y;}
    friend bool operator <=(vct a,vct b)
    {
        if(fabs(a.y-b.y)>eps)//注意这里会产生精度问题
            return a.y<b.y;
        return a.x<b.x;
    }
}p[50010],h[50010],ans[5];
int stk[50010],tp=0;
bool used[50010];
db dis(vct a,vct b,vct x)
{
    return fabs((a-x)*(b-x)/(a-b).dis());
}
vct interact(vct a,vct b,vct c,vct d)//ab∩cd
{
    db s1=(c-a)*(d-a),s2=(d-b)*(c-b);
    return a+(b-a).times(s1/(s1+s2));
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%lf%lf",&p[i].x,&p[i].y);
    std::sort(p+1,p+1+n);
    stk[++tp]=1;
    for(int i=2;i<=n;++i)
    {
        while(tp>1&&(p[stk[tp]]-p[stk[tp-1]])*(p[i]-p[stk[tp]])<=0)
            used[stk[tp--]]=0;
        used[i]=1;
        stk[++tp]=i;
    }
    int qaq=tp;
    for(int i=n-1;i>=1;--i)
        if(!used[i])
        {
            while(tp>qaq&&(p[stk[tp]]-p[stk[tp-1]])*(p[i]-p[stk[tp]])<=0)
                used[stk[tp--]]=0;
            used[i]=1;
            stk[++tp]=i;
        }
    for(int i=1;i<=tp;++i)
        h[i]=p[stk[i]];
    --tp;
    int t=1,t_=1,t__;
    //旋转90° 旋转180° 旋转270°
    while(dis(h[1],h[2],h[t_])<=dis(h[1],h[2],h[t_+1]))
        t_=t_%tp+1;
    t__=t_;
    db Ans=1e15;
    for(int i=1;i<=tp;++i)
    {
        while((h[i+1]-h[i])%(h[t+1]-h[t])>=0)
            t=t%tp+1;
        while(dis(h[i],h[i+1],h[t_])<=dis(h[i],h[i+1],h[t_+1]))
            t_=t_%tp+1;
        while((h[i+1]-h[i])%(h[t__+1]-h[t__])<=0)
            t__=t__%tp+1;
        vct r(-(h[i+1]-h[i]).y,(h[i+1]-h[i]).x);
        db tmp=dis(h[i],h[i+1],h[t_])*dis(h[t],h[t]+r,h[t__]);
        if(tmp<Ans)
        {
            Ans=tmp;
            ans[1]=interact(h[i],h[i+1],h[t],h[t]+r);
            ans[2]=interact(h[t],h[t]+r,h[t_],h[t_]+h[i+1]-h[i]);
            ans[3]=interact(h[t_],h[t_]+h[i+1]-h[i],h[t__],h[t__]+r);
            ans[4]=interact(h[t__],h[t__]+r,h[i],h[i+1]);
        }
    }
    int mn=1;
    for(int i=2;i<=4;++i)
        if(ans[i]<=ans[mn])
            mn=i;
    printf("%.5lf\n",Ans);
    for(int i=1;i<=4;++i)//卡-0.00000
    {
        if(fabs(ans[i].x)<eps)
            ans[i].x=0.0;
        if(fabs(ans[i].y)<eps)
            ans[i].y=0.0;
    }
    for(int i=mn;i<=4;++i)
        printf("%.5lf %.5lf\n",ans[i].x,ans[i].y);
    for(int i=1;i<mn;++i)
        printf("%.5lf %.5lf\n",ans[i].x,ans[i].y);
    return 0;
}