题意：给你一些点，找出两个可以包含所有点的矩形，一个保证矩形面积最小，一个保证矩形周长最小，输出两个最小值
题解：首先根据所有点求一个凸包，再在这个凸包上枚举每条边，作为矩形的一条边（这样可以保证最小）
接着根据旋转卡壳的思想求出另外三条边，这样枚举判断就好
求另三条边时首先方向是确定了的，找点就是旋转卡壳，思想就是：枚举的任意两条边a与b，a的另三条边与b的另三条边都不会再a与b之间，并且b对应边一定最a对应边的 后面（注意是循环的边）那么就是说，我们可以使用类似双指针方式维护，但是时间复杂度却为O（n）
#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<vector> #include<string> #include<cstdio> #include<cstring> #include<iomanip> #include<stdlib.h> #include<iostream> #include<algorithm> using namespace std; #define eps 1E-8 /*注意可能会有输出-0.000*/ #define sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型 #define cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化 #define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0 #define mul(a,b) (a<<b) #define dir(a,b) (a>>b) typedef long long ll; typedef unsigned long long ull; const int Inf=1<<28; const ll INF=1LL<<60; const double Pi=acos(-1.0); const int Mod=1e9+7; const int Max=500010; struct Point { double x,y; Point(double x=0,double y=0):x(x),y(y) {}; inline Point operator-(const Point& a)const { return Point(x-a.x,y-a.y); } inline bool operator<(const Point& a)const { return sgn(x-a.x)<0||zero(x-a.x)&&sgn(y-a.y)<0; } inline Point operator+(const Point& a)const { return Point(x+a.x,y+a.y); } inline bool operator!=(const Point& a)const { return !(zero(x-a.x)&&zero(y-a.y)); } }; typedef Point Vector; struct Line { Point p; Vector v; double ang;//极角 Line() {}; Line(Point p,Vector v):p(p),v(v) { ang=atan2(v.y,v.x); } inline bool operator<(const Line& L)const { return ang<L.ang; } }; double Dis(Point A,Point B) { return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y)); } double Cross(Vector A,Vector B) { return A.x*B.y-A.y*B.x; } int ConvexHull(Point *p,int n,Point *convex)//求凸包 { sort(p,p+n); int m=0; for(int i=0; i<n; ++i) { while(m>1&&Cross(convex[m-1]-convex[m-2],p[i]-convex[m-2])<0) { m--; } convex[m++]=p[i]; } int k=m; for(int i=n-2; i>=0; --i) { while(m>1&&Cross(convex[m-1]-convex[m-2],p[i]-convex[m-2])<0) { m--; } convex[m++]=p[i]; } if(n>1) m--; return m; } Point intersection(Point p1,Point p2,Point l1,Point l2)//交点坐标 { Point ret=p1;//首先计算直线是否平行 double t=((p1.x-l1.x)*(l1.y-l2.y)-(p1.y-l1.y)*(l1.x-l2.x)) /((p1.x-p2.x)*(l1.y-l2.y)-(p1.y-p2.y)*(l1.x-l2.x)); ret.x+=(p2.x-p1.x)*t; ret.y+=(p2.y-p1.y)*t; return ret;//线段交点另外判断线段相交(同时判断是否平行) } Point now[Max],convex[Max]; double area,per; double GetArea(Line up,Line down,Line left,Line right)//根据矩形四条线求面积 { Point minx=intersection(left.p,left.p+left.v,down.p,down.p+down.v); Point miny=intersection(right.p,right.p+right.v,down.p,down.p+down.v); Point manx=intersection(left.p,left.p+left.v,up.p,up.p+up.v); return Dis(minx,manx)*Dis(minx,miny); } double GetPer(Line up,Line down,Line left,Line right) { Point minx=intersection(left.p,left.p+left.v,down.p,down.p+down.v); Point miny=intersection(right.p,right.p+right.v,down.p,down.p+down.v); Point manx=intersection(left.p,left.p+left.v,up.p,up.p+up.v); return (Dis(minx,manx)+Dis(minx,miny))*2; } Vector Rotate(Vector A,double rad) //向量A逆时针旋转rad { return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad)); } void RotateStuck(int n)//旋转卡壳枚举矩形 { for(int i=0;i<n;++i) { convex[i+n]=convex[i]; convex[i+n+n]=convex[i]; } area=per=Inf; Line up,down,left,right;//四条直线 int i=0,j=0,k=0,l=0;//四条线的位置 for(; i<n; ++i)//枚举上这条线，则可以确定其他 { up=Line(convex[i],convex[i+1]-convex[i]);//其他三条直线所在的点与上这条线成单峰函数 k=max(i,k);//每次是逆时针旋转，保证是凸包上一条线或者后面的线 while(Cross(Rotate(up.v,Pi/2),convex[k+1]-convex[k])<0)//通过旋转来判断 k++; left=Line(convex[k],Rotate(up.v,Pi/2)); j=max(k,j); while(Cross(Rotate(up.v,Pi),convex[j+1]-convex[j])<0) j++; down=Line(convex[j],Rotate(up.v,Pi)); l=max(j,l); while(Cross(Rotate(up.v,3*Pi/2),convex[l+1]-convex[l])<0) l++; right=Line(convex[l],Rotate(up.v,3*Pi/2)); area=min(area,GetArea(up,down,left,right)); per=min(per,GetPer(up,down,left,right)); } return ; } int main() { int n; while(~scanf("%d",&n)&&n) { for(int i=0; i<n; ++i) { scanf("%lf %lf",&now[i].x,&now[i].y); } int m= ConvexHull(now,n,convex); RotateStuck(m); printf("%.2f %.2f ",area,per); } return 0; }