BZOJ 1185 [HNOI2007]最小矩形覆盖 旋转卡壳

题意:链接方法:旋转卡壳解析:先求凸包就不说啥了= =!求最小矩形覆盖。有一个显而易见的结论：选择的最小矩阵一定有一条边与凸包上的一条边重合。所以这就有卡壳的资本辣！我们可以枚举在矩阵上的这个边，然后再以这条边找到卡住的相对的最左边的点以及最右边的点，和相对的最上面的点。然后这就是一个矩阵辣！画个图

这图真是治好了我多年的颈椎病2333假设我们枚举到了AB这条边。然后目前的相对的最右边的点是点C，相对的最左边的点是点E，相对的最高点时点D。先说怎么卡壳的吧。首先对于最右边的点来说，卡(qia)的是点积最大，最左边的呢卡的是点积最小的，但是注意一个问题，第一次卡(qia)的时候这个最左边的一定是最高点的后面的点，这是很显然的，不然我们如果遇到前面有点积相同的时候是卡不过去的。所以第一次卡的时候要把最左边的点从最高点开始转。最高点显然就是叉积最大嘛..因为有叉积，我们可以求出来这个矩阵的宽的长度。长怎么求呢？利用点积。我们知道AB的线段长，又知道向量AB与向量AE的点积，所以我们能求出来AE在AB方向上的投影。于是就知道FA辣同理右边可求。然后现在我们求出来了矩阵长和宽，所以就能知道第一问面积了。但是第二问怎么办呢？我们知道点A的坐标，考虑从向量AB的方向开始逆时针找矩阵的四个定点。其实就是把向量乘以下嘛2333.AG我们都知道，所以就把AB乘成AG就知道G辣。其余的同理。于是这题就结束辣。警告前方高能，警告前方高能，警告前方高能警告前方高能，警告前方高能，警告前方高能警告前方高能，警告前方高能，警告前方高能警告前方高能，警告前方高能，警告前方高能警告前方高能，警告前方高能，，警告前方高能警告前方高能，警告前方高能，警告前方高能无意间就插了VFK写的SPJ了怎么办[捂脸熊]直接输出9个nan即可AC哦- -!代码:#include <cstdio>int main(){puts(“nan\nnan nan\nnan nan\nnan nan\nnan nan”);}反正上面程序rnk2(rnk1是大爷抢不过- -!);int n;struct Point{double x,y;< (Point a,Point b){if(a.x==b.x)return a.y<b.y;return a.x<b.x;}friend istream& operator >> (istream &_,Point &a){scanf(“%lf%lf”,&a.x,&a.y);return _;}friend ostream& operator << (ostream &_,Point &a){printf(“%.5lf %.5lf”,a.x,a.y);return _;}Point(){}Point(double _x,double _y):x(_x),y(_y){}Point operator + (const Point &a){return Point(x+a.x,y+a.y);}Point operator – (const Point &a){return Point(x-a.x,y-a.y);}Point operator * (double rate){return Point(x*rate,y*rate);}double operator * (const Point &a){return x*a.x+y*a.y;}double operator ^ (const Point &a){return x*a.y-y*a.x;}}pt[N],sta[N],starc[N],print[4];int top,topp;double Get_Length(Point a){return sqrt(a*a);}double Rotating_Calipers(){double ret=0x7f7f7f7f;int p=1,q=1,r=1;for(int i=0;i<topp;i++){Point a=sta[i+1]-sta[i];double la=Get_Length(a);while(a*(sta[p+1]-sta[i])>a*(sta[p]-sta[i])-eps)p=(p+1)%topp;while(((sta[i+1]-sta[i])^(sta[r+1]-sta[i]))>((sta[i+1]-sta[i])^(sta[r]-sta[i]))-eps)r=(r+1)%topp;if(!i)q=r;while(a*(sta[q+1]-sta[i])<a*(sta[q]-sta[i])+eps)q=(q+1)%topp;double RRR=((sta[p]-sta[i])*(sta[i+1]-sta[i])/la);double LLL=((sta[q]-sta[i])*(sta[i+1]-sta[i])/la);if(LLL<0)LLL=-LLL;double length=LLL+RRR;double height=((sta[i+1]-sta[i])^(sta[r]-sta[i]))/la;if(ret>length*height){ret=length*height;print[0]=sta[i]+(sta[i+1]-sta[i])*(RRR/la);print[1]=print[0]+(sta[p]-print[0])*(height/Get_Length(sta[p]-print[0]));print[2]=print[1]+(sta[r]-print[1])*(length/Get_Length(sta[r]-print[1]));print[3]=print[2]+(sta[q]-print[2])*(height/Get_Length(sta[q]-print[2]));}}return ret;}int main(){scanf(“%d”,&n);for(int i=1;i<=n;i++)cin>>pt[i];sort(pt+1,pt+n+1);topp=-1,top=0;for(int i=1;i<=n;i++){while(top>1&&((starc[top]-starc[top-1])^(pt[i]-starc[top]))<=0)top–;starc[++top]=pt[i];}for(int i=1;i<top;i++){sta[++topp]=starc[i];}top=0;for(int i=1;i<=n;i++){while(top>1&&((starc[top]-starc[top-1])^(pt[i]-starc[top]))>=0)top–;starc[++top]=pt[i];}for(int i=top;i>=1;i–){sta[++topp]=starc[i];}printf(“%.5lf\n”,Rotating_Calipers());int pre=0;for(int i=1;i<=3;i++){if(print[i].y<print[pre].y)pre=i;else if(fabs(print[i].y-print[pre].y)<eps&&print[i].x<print[pre].x)pre=i;}for(int i=0;i<4;i++){cout<<print[(pre+i)%4]<<endl;}}

收敛自己的脾气，偶尔要刻意沉默，