BZOJ1185:[HNOI2007]最小矩形覆盖 凸包+旋转卡壳+三分
思路:
首先有一个显然的性质:就是最小矩形必定有一条边与凸包的边重合.
然后我们自然就是对于每一条边考虑一下:首先找到距离这条边最远的点.然后从这个点到这条边做一条垂线段,用这条垂线段上下平移来得到两个边界.
于是我用旋转卡壳找最远的点,然后对于两边分别三分.
效率好像还不低.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 | #include<cstdio>#include<cstring>#include<cctype>#include<iostream>#include<algorithm>#include<cmath>using namespace std; typedef double f2; static const f2 eps=1e-7;inline int dcmp(const f2&x){return fabs(x)<eps?0:(x<0?-1:1);} #define N 50010struct Point{ f2 x,y; Point(){} Point(f2 _x,f2 _y):x(_x),y(_y){} inline void read(){scanf("%lf%lf",&x,&y);} inline void print(){printf("%.5lf %.5lf\n",x,y);} bool operator<(const Point&B)const{return fabs(x-B.x)==0?y<B.y:x<B.x;} Point operator+(const Point&B)const{return Point(x+B.x,y+B.y);} Point operator-(const Point&B)const{return Point(B.x-x,B.y-y);} Point operator*(const f2&p)const{return Point(x*p,y*p);}}; Point getvec(const Point&v){return Point(-v.y,v.x);}Point getmid(const Point&a,const Point&b){return Point((a.x+b.x)/2,(a.y+b.y)/2);} f2 getdis(const Point&a,const Point&b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}f2 cross(const Point&a,const Point&b){return a.x*b.y-a.y*b.x;}f2 area(const Point&a,const Point&b,const Point&c){return fabs(cross(a-b,a-c))*.5;} struct Line{ Point p,v; Line(Point p1,Point p2,bool d){p=p1,v=d?p1-p2:p2;}}; Point getlineintersection(const Line&l1,const Line&l2){ return l1.p+l1.v*(cross(l1.p-l2.p,l2.v)/cross(l1.v,l2.v));} Point P[N],stk[N<<1];int top; Point move(Point p,Point v,f2 l){ return p+v*(l/sqrt(v.x*v.x+v.y*v.y));} f2 res=1e10;Point re[N]; int main(){ //freopen("tt.in","r",stdin); int n;scanf("%d",&n); register int i,j; for(i=1;i<=n;++i)P[i].read(); sort(P+1,P+n+1); int ins;for(ins=n;ins!=1&&dcmp(P[ins].x-P[ins-1].x)==0;--ins); for(i=ins;i<=(n+ins)/2;++i)swap(P[i],P[n+ins-i]); for(i=1;i<=n;++i){ if(!top)stk[++top]=P[i]; else{while(top>=2&&dcmp(cross(stk[top-1]-stk[top],stk[top]-P[i]))<=0)--top;stk[++top]=P[i];} } int instk=top; for(i=ins-1;i>=1;--i){ if(top==instk)stk[++top]=P[i]; else{while(top>=instk+1&&dcmp(cross(stk[top-1]-stk[top],stk[top]-P[i]))<=0)--top;stk[++top]=P[i];} }--top; for(i=top+1;i<=2*top;++i)stk[i]=stk[i-top]; int r=2,L,R,ll,rr; f2 h1,h2; for(i=1;i<=top;++i){ while(area(stk[i],stk[i+1],stk[r])<=area(stk[i],stk[i+1],stk[r+1]))++r; Line l1=Line(stk[i],stk[i+1],1); Line l2=Line(stk[r],getvec(l1.v),0); Point pr=getlineintersection(l1,l2); h1=h2=0; for(L=i+1,R=r;;){ if(R-L+1<=5){for(j=L;j<=R;++j)h1=max(h1,area(stk[r],pr,stk[j])*2/getdis(stk[r],pr));break;} ll=L+(R-L+1)/3,rr=R-(R-L+1)/3; if(area(stk[r],pr,stk[ll])<=area(stk[r],pr,stk[rr]))L=ll;else R=rr; } for(L=r,R=i+top;;){ if(R-L+1<=5){for(j=L;j<=R;++j)h2=max(h2,area(stk[r],pr,stk[j])*2/getdis(stk[r],pr));break;} ll=L+(R-L+1)/3,rr=R-(R-L+1)/3; if(area(stk[r],pr,stk[ll])<=area(stk[r],pr,stk[rr]))L=ll;else R=rr; } if(getdis(stk[r],pr)*(h1+h2)<res){ res=getdis(stk[r],pr)*(h1+h2); re[0]=move(pr,stk[i]-stk[i+1],h1); re[1]=move(stk[r],stk[i]-stk[i+1],h1); re[2]=move(stk[r],stk[i+1]-stk[i],h2); re[3]=move(pr,stk[i+1]-stk[i],h2); } } printf("%.5lf\n",res); int bins;Point Minre; for(Minre=re[0],bins=0,i=1;i<4;++i)if(dcmp(re[i].y-Minre.y)<0||(dcmp(re[i].y-Minre.y)==0&&dcmp(re[i].x-Minre.x)<0))Minre=re[i],bins=i; for(i=0;i<4;++i)re[(i+bins)%4].print(); return 0;} |
评论 (0)