题意：给出n个矩形，求能覆盖所有矩形的最小的矩形的面积。
题解：对所有点求凸包，然后旋转卡壳，对没一条边求该边的最左最右和最上的三个点。
利用叉积面积求高，利用点积的性质求最左右点和长度，更新面积最小值即可。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define MAX 50010
using namespace std;
struct Point{
double x,y;
Point(double x=,double y=):x(x),y(y){}
};
Point P[MAX],ch[MAX];
typedef Point Vector;
typedef Point point;
Vector operator - (Point A,Point B)
{
return Vector(A.x-B.x,A.y-B.y);
}
bool operator <(const Point &a,const Point &b)
{
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
const double eps=1e-;
int dcmp(double x)
{
if(fabs(x)<eps) return ; else return x<?-:;
}
bool operator ==(const Point &a,const Point &b)
{
return dcmp(a.x-b.x)==&&dcmp(a.y-b.y)==;
}
double Cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
double dot(Vector A,Vector B)
{
return A.x*B.x+A.y*B.y;
}
int ConvexHull(Point *p,int n)
{
sort(p,p+n);
n=unique(p,p+n)-p;
int m=;
for(int i=;i<n;i++)
{
while(m>&&Cross(ch[m-]-ch[m-],p[i]-ch[m-])<=) m--;
ch[m++]=p[i];
}
int k=m;
for(int i=n-;i>=;i--)
{
while(m>k&&Cross(ch[m-]-ch[m-],p[i]-ch[m-])<=) m--;
ch[m++]=p[i];
}
if(n>) m--;
return m;
}
double Length(Vector A)
{
return dot(A,A);
}
double rotating_calipers(Point *p,int n)
{
int l=,r=,w;
double ans=1e30;
p[n]=p[];
for(int i=;i<n;i++)
{
//注意这里等于0一定要算上
//这里debug了整整一个小时 - -|||||
//找到至高点
while(dcmp(Cross(p[i+]-p[i],p[w+]-p[i])-Cross(p[i+]-p[i],p[w]-p[i]))>=) //因为边平行的时候面积相等 虽然如此但还是要继续找下一个 横着爬不动的意思
w=(w+)%n;
//找到最右的点 不可能向左的
while(dcmp(dot(p[i+]-p[i],p[r+]-p[i])-dot(p[i+]-p[i],p[r]-p[i]))>) //凸包不可能凹进去 所以不需要等号 加深对凸包求解过程的理解
r=(r+)%n;
if(i==) l=r;
while(dcmp(dot(p[i+]-p[i],p[l+]-p[i])-dot(p[i+]-p[i],p[l]-p[i]))<=) //必须加等号 否则凸包遇到直边的时候拐不过来 上不去 第二组样例可以完美说明问题
l=(l+)%n;
double d=Length(p[i+]-p[i]);
double area=fabs(Cross(p[i+]-p[i],p[w]-p[i]))
*fabs(dot(p[i+]-p[i],p[r]-p[i])-dot(p[i+]-p[i],p[l]-p[i]))/d;
//cout<<fabs(Cross(p[i+1]-p[i],p[w]-p[i]))<<" "; 这里灵活运用点积求底边长度 上面那一整行化简后就是底边长度
//cout<<"rrrrr "<<r<<" lll "<<l<<endl;
//cout<<dot(p[i+1]-p[i],p[r]-p[i])<<" "<<dot(p[i+1]-p[i],p[l]-p[i])<<endl;
ans=min(ans,area);
}
return ans;
}
int main()
{
int t,n,cas=;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
n*=;
for(int i=;i<n;i++)
scanf("%lf%lf",&P[i].x,&P[i].y);
int m=ConvexHull(P,n);
//for(int i=0;i<n;i++)
//cout<<ch[i].x<<" "<<ch[i].y<<endl;
double ans;
if(m<) ans=;
else ans=rotating_calipers(ch,m);
long long tmp = ans+0.5;
printf("Case #%d:\n%lld\n",cas++,tmp);
}
return ;
}
分析过程：
