【写在前面】：
这应该是我会的第二种计算几何算法(第一种显然是凸包...)，然后感觉还是要记一下比较好
【定义】：
是解决一些与凸包有关问题的有效算法 就像一对卡壳卡住凸包旋转而得名
【对踵点】(from http://www.cnblogs.com/Booble/archive/2011/04/03/2004865.html)：
被一对卡壳正好卡住的对应点对称为对踵点(Antipodal point)
可以证明对踵点的个数不超过3N/2个 也就是说对踵点的个数是O(N)的
对踵点的个数也是我们下面解决问题时间复杂度的保证
这是旋转卡壳的关键所在(下面给几幅图):
上第一个图是卡壳的一般情况 卡住两点 图二是卡住一条边和一个点
由于实现中 卡住两点的情况不好处理 我们通常关注第二种情况
在第二种情况中 我们可以看到 一个对踵点和对应边之间的距离比其他点要大
也就是一个对踵点和对应边所形成的三角形是最大的 下面我们会据此得到对踵点的简化求法
【凸包的直径】
显然直径一定是对踵点间的最大距离
然后关键就是要找出对锺点
我们可以枚举一条边，然后找出距离这条边最远的点
然后如果依次枚举的话复杂度还是O(N^2)的
然后我们可以发现，随着枚举的边顺时针旋转是，最远点也在顺时针移动，因此我们就可以在O(N)时间内求出答案...
【点集的最大三角形】
显然O(N^3)可以暴力
显然，三角形的三个顶点一定在凸包上
其次，我们可以枚举凸包上的两个点，然后就变成求出距离这条边距离最大的点，然后就可以用求凸包直径的方法求出来了
然而这样的时间复杂度还是O(N^3)
但是我们又发现，假设枚举定一个点，那么第三个点是随着第二个点的顺时针旋转而旋转的，因此我们就不需要把旋转卡壳拿出来做，直接与枚举的第二个点一起做，这样时间复杂度就是O(N^2)
【点集的最大四边形】：
其实和三角形没什么太大的区别，旋转卡壳时同时维护枚举的点两边点集的最大三角形，相加即可
但是细节比较多，比如旋转的两个点不能在枚举两个点的同一侧，这样的话就便成凹四边形了...
【两个凸包的最近距离】：
旋转卡壳，去第一个考虑如下的算法， 算法的输入是两个分别有m和n个顺时针给定顶点的凸多边形P和Q。
1.计算P上y坐标值最小的顶点（称为 yminP ）和Q上y坐标值最大的顶点（称为 ymaxQ）。
2.为多边形在 yminP 和 ymaxQ 处构造两条切线 LP 和 LQ 使得他们对应的多边形位于他们的右侧。
此时 LP 和 LQ 拥有不同的方向， 并且 yminP 和 ymaxQ 成为了多边形间的一个对踵点对。
3.计算距离(yminP,ymaxQ) 并且将其维护为当前最小值。
4.顺时针同时旋转平行线直到其中一个与其所在的多边形的边重合。
5.如果只有一条线与边重合， 那么只需要计算“顶点-边”对踵点对和“顶点-顶点”对踵点对距离。 都将他们与当前最小值
比较， 如果小于当前最小值则进行替换更新。如果两条切线都与边重合，那么情况就更加复杂了。如果边“交叠”，也就是
可以构造一条与两条边都相交的公垂线（但不是在顶点处相交）， 那么就计算“边-边”距离。 否则计算三个新的“顶点-顶
点”对踵点对距离。 所有的这些距离都与当前最小值进行比较， 若小于当前最小值则更新替换。
6.重复执行步骤4和步骤5， 直到新的点对为(yminP,ymaxQ)。
7.输出最小距离。
但是细节太多了，在代码里标注了...
【凸多边形最小面积外接矩形】
首先要明确一点：最小面积的外接矩形的某一条边一定与凸多边形的一边重合，然后就好做了
计算全部四个多边形的端点， 称之为 xminP， xmaxP， yminP， ymaxP。
通过四个点构造 P 的四条切线。 他们确定了两个“卡壳”集合。
如果一条（或两条）线与一条边重合，那么计算由四条线决定的矩形的面积， 并且保存为当前最小值。 否则将当前最小值定义为无穷大。
顺时针旋转线直到其中一条和多边形的一条边重合。
计算新矩形的面积， 并且和当前最小值比较。 如果小于当前最小值则更新， 并保存确定最小值的矩形信息。
重复步骤4和步骤5， 直到线旋转过的角度大于90度。
输出外接矩形的最小面积。
然后就是灵活运用向量是很重要的，比如求外接矩形的面积，以及求某两条直线的交点，并且用向量可以保证精度例题：
poj 2187最远点对模板
poj 2079最大三角形
bzoj 1069最大土地面积
poj 3608凸包最近距离
bzoj 1185最小矩形覆盖未完待续...
poj 2187#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#define sqr(x) ((x)*(x))
using namespace std;
const int N=50005;
const double zero=1e-8;
struct point {double x,y;} a[N],stack[N];
int n,top,ans,tot;
point operator -(const point &a,const point &b) {point c; c.x=a.x-b.x; c.y=a.y-b.y; return c;}
double operator *(const point &a,const point &b) {return a.x*b.y-a.y*b.x;}
inline int dist(const point &a,const point &b) {return sqr(a.x-b.x)+sqr(a.y-b.y);}
inline int dcmp(double x) {if (fabs(x)<zero) return 0; if (x>0) return 1; return -1;}
inline bool cmp(point x,point y)
{
double dir=(x-a[1])*(y-a[1]);
int disx=dist(a[1],x),disy=dist(a[1],y);
if (dcmp(dir)==0) return disx>disy;
if (dir<0) return false; else return true;
}
inline long long getint()
{
long long x=0; char c=getchar(); bool flag=false;
while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
if (c=='-') flag=true,c=getchar();
while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
if (flag) return -x; else return x;
}
void init()
{
n=getint(); top=0; ans=0;
for (int i=1; i<=n; i++)
{
a[i].x=getint(); a[i].y=getint();
if ((dcmp(a[i].x-a[1].x)<0)||((dcmp(a[i].x-a[1].x)==0)&&(dcmp(a[i].y-a[1].y)<0))) swap(a[1],a[i]);
}
}
void calc()
{
sort(a+2,a+n+1,cmp); tot=2;
for (int i=3; i<=n; i++) if (dcmp((a[i]-a[1])*(a[i-1]-a[1]))!=0) a[++tot]=a[i];
for (int i=1; i<=tot; i++)
{
while ((top>1)&&(dcmp((stack[top]-stack[top-1])*(a[i]-stack[top]))<0)) top--;
stack[++top]=a[i];
}
}
void solve()
{
stack[top+1]=stack[1]; int now=2;
for (int i=1; i<=top; i++)
{
while (true)
{
double x=fabs((stack[now]-stack[i])*(stack[now]-stack[i+1]));
double y=fabs((stack[now+1]-stack[i])*(stack[now+1]-stack[i+1]));
if (dcmp(x-y)>=0) break; now++; if (now>top) now=1;
}
ans=max(ans,dist(stack[now],stack[i]));
}
printf("%d\n",ans);
}
int main()
{
init();
calc();
solve();
return 0;
}poj 2079
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#define sqr(x) ((x)*(x))
using namespace std;
const int N=50005;
const double zero=1e-8;
struct point {int x,y;} a[N],stack[N];
int n,top,tot,ans;
point operator -(const point &a,const point &b) {point c; c.x=a.x-b.x; c.y=a.y-b.y; return c;}
int operator *(const point &a,const point &b) {return a.x*b.y-a.y*b.x;}
inline int dist(const point &a,const point &b) {return sqr(a.x-b.x)+sqr(a.y-b.y);}
inline bool cmp(point x,point y)
{
int dir=(x-a[1])*(y-a[1]);
if (dir==0) return dist(a[1],x)>dist(a[1],y);
return dir>0;
}
inline long long getint()
{
long long x=0; char c=getchar(); bool flag=false;
while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
if (c=='-') flag=true,c=getchar();
while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
if (flag) return -x; else return x;
}
void init()
{
top=0; ans=0;
for (int i=1; i<=n; i++) a[i].x=getint(),a[i].y=getint();
for (int i=2; i<=n; i++) if ((a[i].x<a[1].x)||((a[i].x==a[1].x)&&(a[i].y<a[1].y))) swap(a[i],a[1]);
}
void calc()
{
sort(a+2,a+n+1,cmp); tot=2; top=0;
for (int i=3; i<=n; i++) if ((a[i]-a[1])*(a[i-1]-a[1])!=0) a[++tot]=a[i];
for (int i=1; i<=tot; i++)
{
while ((top>1)&&((stack[top]-stack[top-1])*(a[i]-stack[top])<0)) top--;
stack[++top]=a[i];
}
}
void solve()
{
stack[top+1]=stack[1];
for (int i=1; i<=top-1; i++)
{
int now=i+1,sx,sy;
for (int j=i+1; j<=top; j++)
{
while (true)
{
sx=abs((stack[now]-stack[i])*(stack[now]-stack[j]));
sy=abs((stack[now+1]-stack[i])*(stack[now+1]-stack[j]));
if (sx>=sy) break; now++; if (now>top) now=1;
}
ans=max(ans,sx);
}
}
printf("%.2lf\n",(double)ans/2);
}
int main()
{
while ((n=getint())!=-1)
{
init();
calc();
solve();
}
return 0;
}bzoj1069
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#define sqr(x) ((x)*(x))
using namespace std;
const int N=2005;
const double zero=1e-8;
struct point {double x,y;} a[N],stack[N*3];
int n,top,tot; double ans,nowans[N];
point operator -(const point &a,const point &b) {point c; c.x=a.x-b.x; c.y=a.y-b.y; return c;}
double operator *(const point &a,const point &b) {return a.x*b.y-a.y*b.x;}
inline double dist(const point &a,const point &b) {return sqr(a.x-b.x)+sqr(a.y-b.y);}
inline int dcmp(double x) {if (x>zero) return 1; else if (x<-zero) return -1; else return 0;}
inline bool cmp(point x,point y)
{
int dir=dcmp((x-a[1])*(y-a[1]));
if (dir==0) return dcmp(dist(a[1],x)-dist(a[1],y))>0;
return dir>0;
}
inline long long getint()
{
long long x=0; char c=getchar(); bool flag=false;
while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
if (c=='-') flag=true,c=getchar();
while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
if (flag) return -x; else return x;
}
void init()
{
n=getint(); top=0; ans=0;
for (int i=1; i<=n; i++) scanf("%lf %lf",&a[i].x,&a[i].y);
for (int i=2; i<=n; i++)
{
if (dcmp(a[i].x-a[1].x)>0) continue;
if ((dcmp(a[i].x-a[1].x)==0)&&(dcmp(a[i].y-a[1].y)>0)) continue;
swap(a[i],a[1]);
}
}
void calc()
{
sort(a+2,a+n+1,cmp); tot=2; top=0;
for (int i=3; i<=n; i++) if (dcmp((a[i]-a[1])*(a[i-1]-a[1]))!=0) a[++tot]=a[i];
for (int i=1; i<=tot; i++)
{
while ((top>1)&&(dcmp((stack[top]-stack[top-1])*(a[i]-stack[top]))<0)) top--;
stack[++top]=a[i];
}
}
void solve()
{
//for (int i=1; i<=top; i++) stack[top+i]=stack[i];
//for (int i=1; i<=top; i++) stack[top+top+i]=stack[i];
stack[top+1]=stack[1];
for (int i=1; i<=top; i++)
{
int now1=i%top+1,now2=i; double sx1,sy1,sx2,sy2;
for (int j=i+1; j<=top; j++)
{
//while (now1<j) now1++;
while (true)
{
if ((now1+1<j)&&(now1+1>i)) break;
sx1=fabs((stack[now1]-stack[i])*(stack[now1]-stack[j]));
sy1=fabs((stack[now1+1]-stack[i])*(stack[now1+1]-stack[j]));
if (sx1>=sy1) break; now1++; if (now1>top) now1=1;
}
while (true)
{
if ((now2+1>j)||(now2+1<i)) break;
sx2=fabs((stack[now2]-stack[i])*(stack[now2]-stack[j]));
sy2=fabs((stack[now2+1]-stack[i])*(stack[now2+1]-stack[j]));
if (sx2>=sy2) break; now2++; if (now2>top) now2=1;
}
ans=max(ans,sx1+sx2);
//if (ans/2>23.5) {printf("%d %d %d %d %.3lf\n",i,now2,j,now1,ans/2);}
}
//memset(nowans,0,sizeof(nowans)); int now=i+1;
//for (int i=j+1)
}
printf("%.3lf\n",ans/2);
}
int main()
{
init();
calc();
solve();
return 0;
}#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#define sqr(x) ((x)*(x))
using namespace std;
const int N=10005;
const double zero=1e-8;
const double INF=3208320832083208.0;
struct point {double x,y;} a[N],b[N],stack[N];
int n,m,top,tot; double ans;
point operator -(const point &a,const point &b) {point c; c.x=a.x-b.x; c.y=a.y-b.y; return c;}
double operator *(const point &a,const point &b) {return a.x*b.y-a.y*b.x;}
inline double dist(const point &a,const point &b) {return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
inline int dcmp(double x) {if (x>zero) return 1; else if (x<-zero) return -1; else return 0;}
inline double muti(const point &a,const point &b) {return a.x*b.x+a.y*b.y;}
inline bool cmp(point x,point y)
{
int dir=dcmp((x-a[1])*(y-a[1]));
if (dir==0) return dcmp(dist(a[1],x)-dist(a[1],y))>0;
return dir>0;
}
inline void change()
{
int now=max(n,m); swap(n,m);
for (int i=1; i<=now; i++) swap(a[i],b[i]);
}
inline double line(point x,point y,point z)
{
if (dcmp(muti(x-y,z-y))<0) return dist(x,y);
if (dcmp(muti(x-z,y-z))<0) return dist(x,z);
double area=(y-z)*(x-z); area=fabs(area);
return area/dist(y,z);
}
inline long long getint()
{
long long x=0; char c=getchar(); bool flag=false;
while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
if (c=='-') flag=true,c=getchar();
while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
if (flag) return -x; else return x;
}
void init()
{
ans=INF; memset(a,0,sizeof(a)); memset(b,0,sizeof(b));
for (int i=1; i<=n; i++) scanf("%lf %lf",&a[i].x,&a[i].y);
for (int i=1; i<=m; i++) scanf("%lf %lf",&b[i].x,&b[i].y);
}
void calc()
{
for (int i=2; i<=n; i++)
{
if (dcmp(a[i].x-a[1].x)>0) continue;
if ((dcmp(a[i].x-a[1].x)==0)&&(dcmp(a[i].y-a[1].y)>0)) continue;
swap(a[i],a[1]);
}
sort(a+2,a+n+1,cmp); tot=2; top=0;
for (int i=3; i<=n; i++) if (dcmp((a[i]-a[1])*(a[i-1]-a[1]))!=0) a[++tot]=a[i];
for (int i=1; i<=tot; i++)
{
while ((top>1)&&(dcmp((stack[top]-stack[top-1])*(a[i]-stack[top]))<0)) top--;
stack[++top]=a[i];
}
n=top; for (int i=1; i<=n; i++) a[i]=stack[i];
}
void getans()
{
int now1=1,now2=1; a[n+1]=a[1]; b[m+1]=b[1];
for (int i=1; i<=n; i++) if (a[i].y<a[now1].y) now1=i;
for (int i=1; i<=m; i++) if (b[i].y>b[now2].y) now2=i;
for (int i=1; i<=n; i++)
{
double sx,sy; int dir;
while (true)
{
sx=(a[now1]-b[now2])*(a[now1+1]-b[now2]);
sy=(a[now1]-b[now2+1])*(a[now1+1]-b[now2+1]); //这两句话不能变，即a[now],a[now+1],b[now],b[now+1]的顺序不能改变!!!
dir=dcmp(sx-sy); if (dir>=0) break; now2=now2%m+1;
}
ans=min(ans,line(a[now1],b[now2],b[now2+1]));
ans=min(ans,line(a[now1+1],b[now2],b[now2+1]));
ans=min(ans,line(b[now2],a[now1],a[now1+1]));
ans=min(ans,line(b[now2+1],a[now1],a[now1+1]));
now1=now1%n+1;
}
}
void solve()
{
calc(); change(); calc();
getans(); change(); getans();
printf("%.5lf\n",ans);
}
int main()
{
while (((n=getint())+(m=getint()))!=0)
{
init();
solve();
}
return 0;
}bzoj 1185
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#define sqr(x) ((x)*(x))
using namespace std;
const int N=50005;
const double zero=1e-8;
struct point {double x,y;} a[N],stack[N];
int n,top,tot; double ans; point anss[5];
point operator -(const point &a,const point &b) {point c; c.x=a.x-b.x; c.y=a.y-b.y; return c;}
point operator &(const point &a,double b) {point c; c.x=a.x*b; c.y=a.y*b; return c;}
point operator +(const point &a,const point &b) {point c; c.x=a.x+b.x; c.y=a.y+b.y; return c;}
double operator *(const point &a,const point &b) {return a.x*b.y-a.y*b.x;}
double operator ^(const point &a,const point &b) {return a.x*b.x+a.y*b.y;}
inline int dcmp(double x) {if (x>zero) return 1; else if (x<-zero) return -1; else return 0;}
inline double dist(const point &a,const point &b) {return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
inline bool cmp(point x,point y)
{
int dir=dcmp((x-a[1])*(y-a[1]));
if (dir==0) return dcmp(dist(x,a[1])-dist(y,a[1]))>0;
return dir>0;
}
inline bool cmps(point x,point y)
{
int dir=dcmp((x-anss[1])*(y-anss[1]));
if (dir==0) return dcmp(dist(x,anss[1])-dist(y,anss[1]))>0;
return dir>0;
}
inline long long getint()
{
long long x=0; char c=getchar(); bool flag=false;
while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
if (c=='-') flag=true,c=getchar();
while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
if (flag) return -x; else return x;
}
void init()
{
n=getint(); ans=320832083208.0;
for (int i=1; i<=n; i++) scanf("%lf %lf",&a[i].x,&a[i].y);
}
void calc()
{
for (int i=2; i<=n; i++)
{
if (dcmp(a[i].x-a[1].x)>0) continue;
if ((dcmp(a[i].x-a[1].x)==0)&&(dcmp(a[i].y-a[1].y)>0)) continue;
swap(a[i],a[1]);
}
sort(a+2,a+n+1,cmp); tot=2; top=0;
for (int i=3; i<=n; i++) if (dcmp((a[i]-a[1])*(a[i-1]-a[1]))!=0) a[++tot]=a[i];
for (int i=1; i<=tot; i++)
{
while ((top>1)&&(dcmp((stack[top]-stack[top-1])*(a[i]-stack[top]))<0)) top--;
stack[++top]=a[i];
}
}
void solve()
{
if (top<3)
{
printf("0\n");
for (int i=1; i<=4; i++) printf("0 0\n");
return;
}
int u=2,r=2,l; stack[top+1]=stack[1];
for (int i=1; i<=top; i++)
{
while (true)
{
double sx=fabs((stack[i]-stack[u])*(stack[i+1]-stack[u]));
double sy=fabs((stack[i]-stack[u+1])*(stack[i+1]-stack[u+1]));
if (dcmp(sx-sy)>0) break; u=u%top+1;
}
while (true)
{
double sx=(stack[r]-stack[i])^(stack[i+1]-stack[i]);
double sy=(stack[r+1]-stack[i])^(stack[i+1]-stack[i]);
if (dcmp(sx-sy)>0) break; r=r%top+1;
}
if (i==1) l=r;
while (true)
{
double sx=(stack[l]-stack[i])^(stack[i+1]-stack[i]);
double sy=(stack[l+1]-stack[i])^(stack[i+1]-stack[i]);
if (dcmp(sx-sy)<0) break; l=l%top+1;
}
double dis=dist(stack[i],stack[i+1]);
double area=fabs((stack[i]-stack[u])*(stack[i+1]-stack[u]));
double L=fabs((stack[r]-stack[i])^(stack[i+1]-stack[i]))+fabs((stack[l]-stack[i])^(stack[i+1]-stack[i]));
double H=area/dis; double nowans=L*H/dis;
if (nowans>=ans) continue; ans=nowans;
anss[1]=stack[i]+((stack[i+1]-stack[i])&(fabs((stack[r]-stack[i])^(stack[i+1]-stack[i]))/dis/dis));
anss[2]=anss[1]+((stack[r]-anss[1])&(H/dist(stack[r],anss[1])));
anss[3]=anss[2]+((stack[u]-anss[2])&(L/dis/dist(stack[u],anss[2])));
anss[4]=anss[3]+((stack[l]-anss[3])&(H/dist(stack[l],anss[3])));
}
printf("%.5lf\n",ans);
for (int i=2; i<=4; i++)
{
if (dcmp(anss[i].y-anss[1].y)>0) continue;
if ((dcmp(anss[i].y-anss[1].y)==0)&&(dcmp(anss[i].x-anss[1].x)>0)) continue;
swap(anss[i],anss[1]);
}
sort(anss+2,anss+5,cmps);
for (int i=1; i<=4; i++)
{
if (dcmp(anss[i].x)==0) anss[i].x=0;
if (dcmp(anss[i].y)==0) anss[i].y=0;
printf("%.5lf %.5lf\n",anss[i].x,anss[i].y);
}
}
int main()
{
init();
calc();
solve();
return 0;
}
鄂公网安备 42010202000505 号