题目
题目描述
给定一些点的坐标，要求求能够覆盖所有点的最小面积的矩形，输出所求矩形的面积和四个顶点坐标
输入输出格式
输入格式：
第一行为一个整数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.000
题解
首先这个矩形的一条边肯定在凸包的一条边$l$所在的直线上，那么另一条对应的边肯定经过距$l$最远的凸包上的点（$l$两端点的对踵点）
然后瞎搞就行了……思路还是很好想的，多利用单调性即可
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<cmath>
# include<algorithm>
using namespace std;
const int MAX=5e4+5;
const double fs=1e-10;
struct Point{
double x,y;
Point(double X=0,double Y=0) {x=X,y=Y;}
bool operator< (const Point &a)
const{
if(y!=a.y) return y<a.y;
return x<a.x;
}
}_P[MAX],_P_[4];
struct Line{
Point a,b;
double L;
Line(){}
Line(Point A,Point B,double _L=0) {a=A,b=B,L=_L;}
};
int n,Top;
double ans=1e18;
int st[MAX];
Point operator+ (Point x,Point y) {return Point(x.x+y.x,x.y+y.y);}
Point operator- (Point x,Point y) {return Point(x.x-y.x,x.y-y.y);}
Point operator* (Point x,double y) {return Point(x.x*y,x.y*y);}
Point operator/ (Point x,double y) {return Point(x.x/y,x.y/y);}
double Cross(Point x,Point y) {return x.x*y.y-x.y*y.x;}
double Cmp(Point a,Point b,Point c) {return Cross(b-a,c-a);}
bool cmp(Point a,Point b)
{
if(fabs(Cmp(_P[1],a,b))<fs) return a.x<b.x;
return Cmp(_P[1],a,b)>0;
}
double GET_DIS(Point a,Point b) {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
double GET_LINE(Point a,Line b) {return fabs(Cross(a-b.a,b.b))/b.L;}
Point GET_POINT(Line a,Line b)
{
a.b=a.a+a.b,b.b=b.a+b.b;
double _k,__k,_b,__b;
Point ans;
if(b.a.x==b.b.x) swap(a,b);
if(a.a.x==a.b.x) return __k=(b.b.y-b.a.y)/(b.b.x-b.a.x),__b=b.a.y-__k*b.a.x,Point(a.a.x,__k*a.a.x+__b);
_k=(a.b.y-a.a.y)/(a.b.x-a.a.x),_b=a.a.y-_k*a.a.x,__k=(b.b.y-b.a.y)/(b.b.x-b.a.x),__b=b.a.y-__k*b.a.x;
return ans.x=(__b-_b)/(_k-__k),ans.y=_k*ans.x+_b,ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%lf%lf",&_P[i].x,&_P[i].y);
sort(_P+1,_P+1+n),st[Top=1]=1,sort(_P+2,_P+1+n,cmp);
for(int i=2;i<=n;++i)
{
while(Top>1&&Cross(_P[st[Top]]-_P[st[Top-1]],_P[i]-_P[st[Top]])<=0) --Top;
st[++Top]=i;
}
st[Top+1]=st[1];
for(int i=1,L=3,_L=0,__L=0;i<=Top;++i)
{
while(Cmp(_P[st[i]],_P[st[i+1]],_P[st[L]])<Cmp(_P[st[i]],_P[st[i+1]],_P[st[L+1]])) L=L%Top+1;
Line L1=Line(_P[st[i]],_P[st[i+1]]-_P[st[i]],GET_DIS(_P[st[i]],_P[st[i+1]])),L2;
Point A=Point(L1.b.y,-L1.b.x),B;
L2=Line(_P[st[L]],A,GET_DIS(_P[st[L]],_P[st[L]]+A)),B=GET_POINT(L1,L2);
double D=GET_LINE(_P[st[L]],L1);
if(_L<i+1) _L=i%Top+1;
if(__L<L) __L=L;
while(_L!=L&&Cmp(_P[st[i]],_P[st[_L]],_P[st[L]])<Cmp(_P[st[i]],_P[st[_L+1]],_P[st[L]])) _L=_L%Top+1;
while(__L!=i&&Cmp(_P[st[i+1]],_P[st[L]],_P[st[__L]])<Cmp(_P[st[i+1]],_P[st[L]],_P[st[__L+1]])) __L=__L%Top+1;
double _D=GET_LINE(_P[st[_L]],L2),__D=GET_LINE(_P[st[__L]],L2);
if(ans<=D*(_D+__D)) continue;
ans=D*(_D+__D);
Line L3=Line(_P[st[_L]],A),L4=Line(_P[st[__L]],A),L5=Line(_P[st[L]],L1.b);
_P_[0]=GET_POINT(L1,L3),_P_[1]=GET_POINT(L1,L4),_P_[2]=GET_POINT(L5,L3),_P_[3]=GET_POINT(L5,L4);
}
printf("%.5lf\n",ans);
for(int i=0;i<4;++i)
_P[i+1]=_P_[i];
sort(_P+1,_P+5),st[Top=1]=1,sort(_P+2,_P+5,cmp);
for(int i=1;i<=4;++i)
{
while(Top>1&&Cross(_P[st[Top]]-_P[st[Top-1]],_P[i]-_P[st[Top]])<=0) --Top;
st[++Top]=i;
}
for(int i=1;i<=4;++i)
printf("%.5lf %.5lf\n",_P[st[i]].x+fs,_P[st[i]].y+fs);
return 0;
}
