【最小矩形面积覆盖：凸包+旋转卡壳】UVA 10173Smallest Bounding Rectangle
分类：计算几何
【最小矩形面积覆盖：凸包+旋转卡壳】UVA 10173 Smallest Bounding Rectangle题目链接：UVA 10173 Smallest Bounding Rectangle题目大意
给你n个点，求能够覆盖所有点集的最小矩形面积。
笔者的第2道凸包题目，凸包 + 旋转卡壳，实现点集的最小矩形面积覆盖问题 “>=0”写成”<=0“坑了我一下午！QAQ
说一下思路①Graham’s Scan法构建凸包，时间复杂度O(nlogn)②利用旋转卡壳的思想，，最小矩形至少存在一条边与凸包共线。所以直接枚举底边，利用旋转卡壳确定其余三个点即可（kuangbin的最小矩形覆盖模板，但操作函数我在结构体外定义，省空间！）参考代码/*====================================*\|*最小矩形面积覆盖*||* 多边形A必须是凸包(默认：逆时针顺序)*|\*====================================*/;const int _max = 1e3 + 10;const double PI = acos(-1);int n;;else return x<0?-1:1;}struct point{double x,y;}p[_max],res[_max];bool mult(point sp,point ep,point op){ return (sp.x – op.x) * (ep.y – op.y)>= (ep.x – op.x) * (sp.y – op.y);}bool operator < (const point &l, const point &r){ return l.y < r.y ||(l.y == r.y && l.x < r.x);}int graham(point pnt[],int n, point res[]){//构造凸包 int i,len ,k = 0,top = 1; sort(pnt,pnt+n); if(n == 0)return 0; res[0] = pnt[0]; if(n == 1)return 1; res[1] = pnt[1]; if(n == 2)return 2; res[2] = pnt[2]; for(int i =2; i < n; ++ i){while(top && mult(pnt[i],res[top],res[top-1]))top–;res[++top] = pnt[i]; } len = top; res[++top] = pnt[n – 2]; for(i = n – 3; i >= 0; — i){while(top!=len && mult(pnt[i],res[top],res[top-1]))top–;res[++top] = pnt[i]; } return top;//返回凸包中点的个数}double len(point A,point B){//返回向量AB的模平方 return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);}double dot(point A,point B,point C){//点乘 return (C.x-A.x)*(B.x-A.x)+(C.y-A.y)*(B.y-A.y);}double cross(point A,point B,point C){//叉乘 return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);}; res[n] = res [0]; double ans = -1; int r = 1, p = 1,q; for(int i = 0; i < n; ++ i){//卡出离边 res[i]-res[i+1]最远的点while(sgn(cross(res[i],res[i+1],res[r+1])-cross(res[i],res[i+1],res[r]))>=0)r = (r+1)% n;//卡出res[i]-res[i+1]方向上正向n最远的点while(sgn(dot(res[i],res[i+1],res[p+1])-dot(res[i],res[i+1],res[p]))>=0)p = (p+1)% n;if(i == 0) q = p;//卡出res[i]-res[i+1]方向上负向最远的点while(sgn(dot(res[i],res[i+1],res[q+1])-dot(res[i],res[i+1],res[q]))<=0)q = (q+1)% n;double d = len(res[i],res[i+1]);double temp = cross(res[i],res[i+1],res[r])*(dot(res[i],res[i+1],res[p])-dot(res[i],res[i+1],res[q]))/d;if(ans < 0 || ans > temp) ans = temp; } return ans;}int main(){ #ifndef ONLINE_JUDGE freopen(“input.txt”,”r”,stdin); #endif // ONLINE_JUDGE while(scanf(“%d”,&n)==1 && n){for(int i = 0; i < n; ++ i){scanf(“%lf%lf”,&p[i].x,&p[i].y);}n = graham(p,n,res);//构造凸包printf(“%.4f\n”,minRetangleCover()); } return 0;}
爱的力量大到可以使人忘记一切，却又小到连一粒嫉妒的沙石也不能容纳
