[BZOJ1185][HNOI2007]最小矩形覆盖（凸包+旋转卡壳）

题目描述

传送门

题解

首先先求一个凸包，矩形一定是把这个凸包覆盖掉 猜想：最小矩形的某一边一定和凸包的某一边重合 那么如何来证明呢？ 可以用反证法。假设最小矩形不过凸包上的任意一条边，那么凸包最多有4个顶点在矩形上，可分为3种情况 1、凸包有2个顶点在矩形上 假设旋转了外接矩形一个角度，使其与对角线a夹角为 α ，那么新的矩形（用虚线表示）面积S= a2sinαcosα=12a2sin2α ，显然 α<π4 ， 2α<π2 ，此时S单增。所以直接令 α=0 即可，也就是旋转矩形使之与凸包的一条边重合。 2、凸包有3个顶点在矩形上 设ab边的夹角为r，a与矩形的夹角为p，那么矩形的面积可以表示为 S=a∗cosp∗b∗cos(π2−r−p)=ab∗sin(r+p)∗cosp=ab(sinr∗cosp+cosr∗sinp)∗cosp =ab(sinr∗cos2p+cosr∗sinp∗cosp)=12ab[sin2p∗cosr+(cos2p+1)∗sinr] =12ab(sin2p∗cosr+cos2p∗sinr+sinr)=12ab∗[sin(2p+r)+sinr] 假设a>b那么 p∈[0,π4] ，由正弦函数图像可知2p+r值在 [r,r+π2] ，所以只有当p趋近于0或 π4 时取最小值。我们可以认为必须将矩形转过一个角度使p=0或者当a成为矩形对角线使r的对边与矩形的一遍重合时取最小值。 3、凸包有4个顶点在矩形上 假设长边为a短边为b S=a∗sinp∗b∗sin[π−(π2−p)−(π−r)]=−ab∗sinp∗cos(2p+r)=12ab[sinr−sin(2p+r)] 假设r为夹角中的锐角，并且p为锐角且 p>π4 ，当p趋近于 π4 时达到最小值，即还需要将矩形转过一个角度

证明不是很严谨。。似乎还没有感性的理解来的直观？

那么枚举凸包上的边了之后剩下的就需要确定三个边界。 实际上这三个边界可以用三个点来表示，并且这三个点是单调的 这个应该是很显然的吧，对于凸包上的同一条边右边最值、左边最值和点线距一定单峰，每旋转过一条边，这三个点的相对位置一定单调 不过似乎二分/三分更科学一些？ 时间复杂度 O(nlogn)

代码

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; #define N 100005 const double inf=1e60; const double pi=acos(-1.0); const double eps=1e-8; int dcmp(double x) { if (x<=eps&&x>=-eps) return 0; return (x>0)?1:-1; } struct Vector { double x,y; Vector(double X=0,double Y=0) { x=X,y=Y; } bool operator < (const Vector a) const { return x<a.x||(x==a.x&&y<a.y); } }; typedef Vector Point; struct Line { Point p; Vector v; Line(Point P=Point(0,0),Vector V=Vector(0,0)) { p=P,v=V; } }; Vector operator + (Vector a,Vector b) {return Vector(a.x+b.x,a.y+b.y);} Vector operator - (Vector a,Vector b) {return Vector(a.x-b.x,a.y-b.y);} Vector operator * (Vector a,double b) {return Vector(a.x*b,a.y*b);} int n,top; double ans; Point p[N],stack[N],squ[N]; double Dot(Vector a,Vector b) { return a.x*b.x+a.y*b.y; } double Cross(Vector a,Vector b) { return a.x*b.y-a.y*b.x; } double Len(Vector a) { return sqrt(Dot(a,a)); } Vector rotate(Vector a,double rad) { return Vector(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad)); } double DisTL(Point P,Point A,Point B) { Vector v=B-A,w=P-A; return fabs(Cross(v,w)/Len(v)); } Point GLI(Line l,Line m) { Point P=l.p,Q=m.p; Vector v=l.v,w=m.v,u=P-Q; double t=Cross(w,u)/Cross(v,w); return P+v*t; } void graham() { sort(p+1,p+n+1); top=0; for (int i=1;i<=n;++i) { while (top>1&&dcmp(Cross(stack[top]-stack[top-1],p[i]-stack[top-1]))<=0) --top; stack[++top]=p[i]; } int k=top; for (int i=n-1;i>=1;--i) { while (top>k&&dcmp(Cross(stack[top]-stack[top-1],p[i]-stack[top-1]))<=0) --top; stack[++top]=p[i]; } if (n>1) --top; } void update(Point A,Point B,Point C,Point D,Point E) { Vector v,w; Line l1,l2,l3,l4; v=B-A; l1=Line(A,v); l2=Line(D,v); w=rotate(v,pi/2.0); l3=Line(C,w); l4=Line(E,w); double x=DisTL(D,A,A+v); double y=DisTL(C,E,E+w); if (dcmp(x*y-ans)<0) { ans=x*y; squ[1]=GLI(l1,l3); squ[2]=GLI(l2,l3); squ[3]=GLI(l2,l4); squ[4]=GLI(l1,l4); } } void rotating() { if (top==1) { ans=0; for (int i=1;i<=4;++i) squ[i]=stack[1]; return; } if (top==2) { ans=0; squ[1]=squ[2]=stack[1]; squ[3]=squ[4]=stack[2]; return; } int a=2,b=2,c=2; Vector v,w; Line l; for (int i=1;i<=top;++i) { if (a==i) a=a%top+1; v=stack[i%top+1]-stack[i]; w=rotate(v,pi/2.0); l=Line(stack[i%top+1],w); while (a%top+1!=i%top+1&&dcmp(Cross(stack[a%top+1]-stack[i%top+1],w))>=0&&dcmp(DisTL(stack[a%top+1],l.p,l.p+l.v)-DisTL(stack[a],l.p,l.p+l.v))>=0) a=a%top+1; while (b%top+1!=i%top+1&&dcmp(DisTL(stack[b%top+1],stack[i],stack[i%top+1])-DisTL(stack[b],stack[i],stack[i%top+1]))>=0) b=b%top+1; l=Line(stack[i],w); while (c%top+1!=i%top+1&&(dcmp(Cross(stack[c]-stack[i],w))>=0||dcmp(DisTL(stack[c%top+1],l.p,l.p+l.v)-DisTL(stack[c],l.p,l.p+l.v))>=0)) c=c%top+1; update(stack[i],stack[i%top+1],stack[a],stack[b],stack[c]); } } int main() { scanf("%d",&n); for (int i=1;i<=n;++i) scanf("%lf%lf",&p[i].x,&p[i].y); graham(); ans=inf; rotating(); printf("%.5lf\n",ans); int st=1; for (int i=2;i<=4;++i) if (dcmp(squ[i].y-squ[st].y)<0||(dcmp(squ[i].y-squ[st].y)==0&&dcmp(squ[i].x-squ[st].x)<0)) st=i; for (int i=st;i<=4;++i) printf("%.5lf %.5lf\n",squ[i].x,squ[i].y); for (int i=1;i<st;++i) printf("%.5lf %.5lf\n",squ[i].x,squ[i].y); return 0; }