旋转卡壳(一)

1 .最小面积外接矩形

类似的，要求得外接矩形，则要求出矩形的宽和高，而高的求法已经知道了，是利用叉积求面积的方法可以求出高，而宽则可以用点积来求。


先来看看点积的几何意义：


假设Ｓ为旋转卡壳中的枚举边，Ｆ为待定的右边界，那么要使得右边界最右，即右边的宽度（Ｆ*cos(Θ) )越长，则他们的点积要越大
类似的，左边界的点积要越小

矩形面积
题意：
求.最小面积外接矩形

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=4010;
const double EPS=1e-10;
const double INF=1e20;
struct Point
{
    double x,y;
    Point(double x=0,double y=0):x(x),y(y){}
};
Point in[MAXN],out[MAXN];
typedef Point Vector;
bool operator <(const Point &a,const Point &b)
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
Vector operator -(Vector A,Vector B)
{
    return Vector(A.x-B.x,A.y-B.y);
}
double cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}
double dot(Vector A,Vector B)
{
    return A.x*B.x+A.y*B.y;
}
int convexHull(Point *p,int n,Point *ch)
{
    sort(p,p+n);
    int m=0;
    for(int i=0;i<n;i++)
    {
        while(m>1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
        ch[m++]=p[i];
    }
    int k=m;
    for(int i=n-2;i>=0;i--)
    {
        while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
        ch[m++]=p[i];
    }
    if(n>1) m--;
    return m;
}
double length(Vector A)
{
    return sqrt(A.x*A.x+A.y*A.y);
}
double rotateCalipers(Point *p,int n)
{
    int up=1,rig=1,lef;
    p[n]=p[0];
    double ans=INF;
    for(int i=0;i<n;i++)
    {
        while(cross(p[i+1]-p[i],p[up]-p[i])<cross(p[i+1]-p[i],p[up+1]-p[i])) up=(up+1)%n;//上边界
        while(dot(p[i+1]-p[i],p[rig]-p[i])<dot(p[i+1]-p[i],p[rig+1]-p[i])) rig=(rig+1)%n;//右边界
        if(i==0) lef=rig;   
        while(dot(p[i+1]-p[i],p[lef]-p[i])>=dot(p[i+1]-p[i],p[lef+1]-p[i])) lef=(lef+1)%n;//左边界，这里必须有等于号
        double len=length(p[i+1]-p[i]);
        double area=(cross(p[i+1]-p[i],p[up]-p[i])/len)*(dot(p[i+1]-p[i],p[rig]-p[i])/len-dot(p[i+1]-p[i],p[lef]-p[i])/len);
        //cross(p[i+1]-p[i],p[up]-p[i])/len为矩形的高，(dot(p[i+1]-p[i],p[rig]-p[i])/len-dot(p[i+1]-p[i],p[lef]-p[i])/len)为矩形的宽
        //左边界的点积dot(p[i+1]-p[i],p[lef]-p[i])有可能小于0
        if(ans>area) ans=area;
    }
    return ans;
}
int main()
{
    int t,n;
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++)
    {
        scanf("%d",&n);
        n*=4;
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf",&in[i].x,&in[i].y);
        }
        int res=convexHull(in,n,out);
        double area=rotateCalipers(out,res);
        printf("Case #%d:\n%.f\n",cas,area);
    }
}

类似题目：
Smallest Bounding Rectangle
题解：注意要特判，只有一个点的时候直接输出0,如果求旋转卡壳会造成死循环，因为求左边界有等于号的缘故

2.求凸包间的最小距离

原理类似，就是不断求边与边的最短距离就可以了
就是初始化有点不一样：
左边的凸包寻找最低点，右边的凸包寻找最高点


凸包最短距离专用图

Bridge Across Islands
题意：
求凸包间的最短距离

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const double EPS=1e-10;
const double INF=1e20;
const int MAXN=10010;
struct Point
{
    double x,y;
    Point(double x=0,double y=0):x(x),y(y){}
};
Point p1[MAXN],p2[MAXN];
typedef Point Vector;
int dcmp(double val)
{
    if(abs(val)<EPS) return 0;
    return val>0?1:-1;
}
Vector operator-(Vector A,Vector B)
{
    return Vector(A.x-B.x,A.y-B.y);
}
bool operator ==(const Point &a,const Point &b)
{
    return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
}
double cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}
double dot(Vector A,Vector B)
{
    return A.x*B.x+A.y*B.y;
}
double length(Vector A)
{
    return sqrt(A.x*A.x+A.y*A.y);
}
double disToSegment(Point p,Point a,Point b)
{
    if (a==b) return length(p-a);
    if(dcmp(dot(b-a,p-a))<0) return length(p-a);
    else if(dcmp(dot(a-b,p-b))<0) return length(p-b);
    else return abs(cross(p-b,a-b))/length(a-b);
}
double disLineToLine(Point a,Point b,Point c,Point d)//两线段间的最短距离
{
    //对应四种情况
    return min(min(min(disToSegment(a,c,d),disToSegment(b,c,d)),disToSegment(c,a,b)),disToSegment(d,a,b));
}
double rotateCalipers(Point *p,int n,Point *s,int m)
{
    int minp=0,maxs=0;
    for(int i=1;i<n;i++)
    {
        if(p[i].y<p[minp].y) minp=i;
    }
    for(int i=1;i<m;i++)
    {
        if(s[i].y>p[maxs].y) maxs=i;
    }
    p[n]=p[0];
    s[m]=s[0];
    double dis=INF,tmp;
    for(int i=0;i<n;i++)
    {
        //如果maxs+1到边(minp,minp+1)的距离比maxs到边(minp,minp+1)的距离近,那么maxs向前走,距离用的是叉积求三角形面积来判断
        while(cross(p[minp]-p[minp+1],s[maxs+1]-p[minp+1])-cross(p[minp]-p[minp+1],s[maxs]-p[minp+1])<-EPS) maxs=(maxs+1)%m;
        dis=min(dis,disLineToLine(p[minp],p[minp+1],s[maxs],s[maxs+1]));//两线间的最短距离
        minp=(minp+1)%n;
    }
    return dis;
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF,n+m)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf",&p1[i].x,&p1[i].y);
        }
        for(int i=0;i<m;i++)
        {
            scanf("%lf%lf",&p2[i].x,&p2[i].y);
        }
        double dis=rotateCalipers(p1,n,p2,m);
        printf("%.5f\n",dis);
    }
}

3.给定多个点，求任意三点的最大的三角形面积

首先，我们知道最大的三角形的点一定是在多点形成的凸包上，但是最大三角形的边却不一定是凸包的边。
设三个起点i=0，j=1，k=2，每次都先移动k，直到面积最大，然后移动j直到面积最大，然后移动i直到面积最大，因为这个过程中面积是不断增加的，所以移动完在取最大值吧，不用每移动一次都求，如果三个点都不变的话，强制移动k。用vis数组来表示访问状态，当vis[2]时表示已经访问一圈，然后结束循环。
C - Triangle
题意：
求解平面中的点中任意取三个能够形成最大的三角形面积。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const double EPS=1e-10;
const double INF=1e20;
const int MAXN=50010;
struct Point
{
    double x,y;
    Point(double x=0,double y=0):x(x),y(y){}
};
Point in[MAXN],out[MAXN];
typedef Point Vector;
bool operator<(const Point &a,const Point &b)
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
Vector operator -(Vector A,Vector B)
{
    return Vector(A.x-B.x,A.y-B.y);
}
double cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}
double dot(Vector A,Vector B)
{
    return A.x*B.x+A.y*B.y;
}
int convexHull(Point *p,int n,Point *ch)
{
    sort(p,p+n);
    int m=0;
    for(int i=0;i<n;i++)
    {
        while(m>1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
        ch[m++]=p[i];
    }
    int k=m;
    for(int i=n-2;i>=0;i--)
    {
        while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
        ch[m++]=p[i];
    }
    if(n>1) m--;
    return m;
}
int vis[MAXN];
double rotateCalipers(Point *p,int n)
{
    if(n<3) return 0;
    p[n]=p[0];
    int i=0,j=1,k=2,a,b,c;
    double area=-INF,tmp;
    memset(vis,0,sizeof(vis));
    while(!vis[2])
    {
        a=i;b=j;c=k;
        while(cross(p[j]-p[i],p[k]-p[i])<cross(p[j]-p[i],p[k+1]-p[i])) k=(k+1)%n,vis[k]=1;
        while(cross(p[j]-p[i],p[k]-p[i])<cross(p[j+1]-p[i],p[k]-p[i])) j=(j+1)%n;
        while(cross(p[j]-p[i],p[k]-p[i])<cross(p[j]-p[i+1],p[k]-p[i+1])) i=(i+1)%n;
        area=max(area,cross(p[j]-p[i],p[k]-p[i]));
        if(a==i&&b==j&&c==k) k=(k+1)%n,vis[k]=1;
    }
    return area/2;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF,n+1)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf",&in[i].x,&in[i].y);
        }
        int res=convexHull(in,n,out);
        double area=rotateCalipers(out,res);
        printf("%.2f\n",area);
    }
}

还有一种暴力枚举的方法，时间复杂度为O(N^2)就是任意枚举两条边，借助旋转卡壳寻找最大面积三角形

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const double EPS=1e-10;
const double INF=1e20;
const int MAXN=50010;
struct Point
{
    double x,y;
    Point(double x=0,double y=0):x(x),y(y){}
};
Point in[MAXN],out[MAXN];
typedef Point Vector;
bool operator<(const Point &a,const Point &b)
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
Vector operator -(Vector A,Vector B)
{
    return Vector(A.x-B.x,A.y-B.y);
}
double cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}
double dot(Vector A,Vector B)
{
    return A.x*B.x+A.y*B.y;
}
int convexHull(Point *p,int n,Point *ch)
{
    sort(p,p+n);
    int m=0;
    for(int i=0;i<n;i++)
    {
        while(m>1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
        ch[m++]=p[i];
    }
    int k=m;
    for(int i=n-2;i>=0;i--)
    {
        while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
        ch[m++]=p[i];
    }
    if(n>1) m--;
    return m;
}
double rotateCalipers(Point *p,int n)
{
    p[n]=p[0];
    int up;
    double area=-INF,tmp;
    for(int i=0;i<n;i++)//枚举边i,j
    {
        up=i+1;
        for(int j=i+1;j<n;j++)
        {
            while(cross(p[j]-p[i],p[up+1]-p[i])>cross(p[j]-p[i],p[up]-p[i])) up=(up+1)%n;
            tmp=cross(p[j]-p[i],p[up]-p[i]);
            if(tmp>area) area=tmp;
        }
    }
    return area/2;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF,n+1)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf",&in[i].x,&in[i].y);
        }
        int res=convexHull(in,n,out);
        double area=rotateCalipers(out,res);
        printf("%.2f\n",area);
    }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 小学数学知识点
    第一章数和数的运算 一概念 （一）整数 1整数的意义 自然数和0都是整数。 2自然数 我们在数物体的时候，用来表示...
    meychang阅读 2,663评论 0赞 5
  • 2017成都小升初数学考哪些知识点？
    2017年第22届华杯赛初赛眼看着就要来了，翻过年就该2017成都小升初择校了，很多家长在后台问小升初考哪些数学知...
    1a068af8ad5a阅读 585评论 0赞 1
  • 2017成都小升初数学考哪些知识点？
    2017成都小升初数学考哪些知识点 2017年第22届华杯赛初赛眼看着就要来了，翻过年就该2017成都小升初择...
    1a068af8ad5a阅读 704评论 0赞 0
  • 给我爱的你
    从来没有为你写过诗 哪怕一句 我会用缠绵悱恻写一曲爱的悲歌 也曾用山盟海誓创造了爱情神话 他们一定特别好奇 我会用...
    梨子酱欧尼阅读 127评论 4赞 7
  • （一）JavaScript——变量
    学习一门语言，无论是人类的语言，还是阿猫阿狗的语言，甚至是机器的语言，都有其基本的规律和核心要素。就计算机语...
    清葉阅读 175评论 0赞 0