旋转卡壳(一)

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);
    }
}

最后编辑于：2017.12.10 04:29:17

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 197,368评论 5赞 462
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 82,941评论 2赞 374
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 144,369评论 0赞 326
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 52,848评论 1赞 267
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 61,719评论 5赞 358
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 46,505评论 1赞 275
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 36,904评论 3赞 388
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 35,528评论 0赞 254
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 39,819评论 1赞 293
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 34,848评论 2赞 314
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 36,652评论 1赞 328
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 32,468评论 3赞 316
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 37,912评论 3赞 300
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,095评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 30,389评论 1赞 255
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 41,906评论 2赞 343
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 41,120评论 2赞 339

旋转卡壳(一)

1 .最小面积外接矩形

2.求凸包间的最小距离

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

推荐阅读更多精彩内容