标签：计算几何-旋转卡壳
题目
题目描述
给定一些点的坐标，要求求能够覆盖所有点的最小面积的矩形，输出所求矩形的面积和四个顶点坐标 输入输出格式 输入格式：
第一行为一个整数n（3<=n<=50000），从第2至第n+1行每行有两个浮点数，表示一个顶点的x和y坐标，不用科学计数法
输出格式：
第一行为一个浮点数，表示所求矩形的面积（精确到小数点后5位），接下来4行每行表示一个顶点坐标，要求第一行为y坐标最小的顶点，其后按逆时针输出顶点坐标.如果用相同y坐标，先输出最小x坐标的顶点
输入输出样例 输入样例#1： 复制
6 1.0 3.00000
1 4.00000
2.0000 1
3 0.0000
3.00000 6
6.0 3.0
输出样例#1： 复制
18.00000
3.00000 0.00000
6.00000 3.00000
3.00000 6.00000
0.00000 3.00000
分析
题意大概是给出一些点的坐标，求覆盖这组点的最小矩形，并输出矩形四点坐标
结论：矩形的一条边一定在这些点的凸包上
枚举凸包上的边，然后用旋转卡壳找另外三个点
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define eps 1e-9
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=5e4+6;
double ans=1e60;int n,top,k=0;
struct P{
double x,y;
P(){}
P(double _x,double _y):x(_x),y(_y){}
friend bool operator < (P a,P b){return fabs(a.y-b.y)<eps?a.x<b.x:a.y<b.y;}
friend bool operator == (P a,P b){return fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps;}
friend bool operator != (P a,P b){return !(a==b);}
friend P operator + (P a,P b){return P(a.x+b.x,a.y+b.y);}
friend P operator - (P a,P b){return P(a.x-b.x,a.y-b.y);}
friend double operator * (P a,P b){return a.x*b.y-a.y*b.x;}
friend P operator * (P a,double b){return P(a.x*b,a.y*b);}
friend double operator/(P a,P b){return a.x*b.x+a.y*b.y;}
friend double dis(P a){return sqrt(a.x*a.x+a.y*a.y);}
}p[maxn],s[maxn],a[6];
bool cmp(P a,P b){
double t=(a-p[1])*(b-p[1]);
if(fabs(t)<eps)return dis(p[1]-a)-dis(p[1]-b)<0;else return t>0;
}
void graham(){
rep(i,2,n)if(p[i]<p[1])swap(p[i],p[1]);
sort(p+2,p+n+1,cmp);
s[++top]=p[1];
rep(i,2,n){
while(top>1&&((s[top]-s[top-1])*(p[i]-s[top]))<eps)top--;
s[++top]=p[i];
}
s[0]=s[top];
}
void RC(){
int l=1,r=1,p=1;double L,R,D,H;
rep(i,0,top-1){
D=dis(s[i]-s[i+1]);
while((s[i+1]-s[i])*(s[p+1]-s[i])-(s[i+1]-s[i])*(s[p]-s[i])>-eps)p=(p+1)%top;
while((s[i+1]-s[i])/(s[r+1]-s[i])-(s[i+1]-s[i])/(s[r]-s[i])>-eps)r=(r+1)%top;
if(i==0)l=r;
while((s[i+1]-s[i])/(s[l+1]-s[i])-(s[i+1]-s[i])/(s[l]-s[i])<eps)l=(l+1)%top;
L=(s[i+1]-s[i])/(s[l]-s[i])/D,R=(s[i+1]-s[i])/(s[r]-s[i])/D;
H=(s[i+1]-s[i])*(s[p]-s[i])/D;
if(H<0)H=-H;
double tmp=(R-L)*H;
if(tmp<ans){
ans=tmp;
a[0]=s[i]+(s[i+1]-s[i])*(R/D);
a[1]=a[0]+(s[r]-a[0])*(H/dis(a[0]-s[r]));
a[2]=a[1]-(a[0]-s[i])*((R-L)/dis(s[i]-a[0]));
a[3]=a[2]-(a[1]-a[0]);
}
}
}
int main()
{
n=read();
rep(i,1,n)scanf("%lf%lf",&p[i].x,&p[i].y);
graham();RC();
printf("%.5lf\n",ans);
rep(i,1,3)
if(a[i]<a[k])k=i;
rep(i,0,3)printf("%.5lf %.5lf\n",a[(i+k)%4].x,a[(i+k)%4].y);
return 0;
}
