题目链接
题解
最小矩形一定有一条边在凸包上，枚举这条边，然后旋转卡壳维护另外三个端点即可
计算几何细节极多
- 维护另外三个端点尽量不在这条边上，意味着左端点尽量靠后，右端点尽量靠前，加上或减去一个\(eps\)来处理
- \(C++\)中\(printf\)输出\(0.00000\)会变成\(-0.00000\)，需要特判
- 用叉积点乘判距离大小，正负方向不要搞错
- 求凸包记得排序
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#define eps 1e-9
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define cls(s,v) memset(s,v,sizeof(s))
#define mp(a,b) make_pair<int,int>(a,b)
#define cp pair<int,int>
using namespace std;
const int maxn = 50005,maxm = 100005;
const double INF = 1e15;
struct point{double x,y;}p[maxn],G[maxn],t[5];
inline bool operator <(const point& a,const point& b){
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
inline point operator +(const point& a,const point& b){
return (point){a.x + b.x,a.y + b.y};
}
inline point operator -(const point& a,const point& b){
return (point){a.x - b.x,a.y - b.y};
}
inline double operator *(const point& a,const point& b){
return a.x * b.x + a.y * b.y;
}
inline point operator *(const point& a,const double& b){
return (point){a.x * b,a.y * b};
}
inline double cross(const point& a,const point& b){
return a.x * b.y - a.y * b.x;
}
inline double dis(const point& a,const point& b){
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double ans = INF;
int n,st[maxn],top;
void graham(){
sort(p + 1,p + 1 + n);
for (int i = 1; i <= n; i++){
while (top > 1 && cross(p[st[top]] - p[st[top - 1]],p[i] - p[st[top]]) >= 0) top--;
st[++top] = i;
}
int tmp = top;
for (int i = n - 1; i; i--){
while (top > tmp && cross(p[st[top]] - p[st[top - 1]],p[i] - p[st[top]]) >= 0) top--;
st[++top] = i;
}
top--;
REP(i,top) G[i - 1] = p[st[i]];
G[top] = G[0];
}
void work(){
int d,l,r; d = l = r = 1;
double L,R,D,H;
for (int i = 0; i < top; i++){
D = dis(G[i],G[i + 1]);
while (cross(G[d + 1] - G[i],G[i + 1] - G[i]) + eps >= cross(G[d] - G[i],G[i + 1] - G[i])) d = (d + 1) % top;
while ((G[i + 1] - G[i]) * (G[l + 1] - G[i + 1]) + eps >= (G[i + 1] - G[i]) * (G[l] - G[i + 1])) l = (l + 1) % top;
if (i == 0) r = d;
while ((G[i] - G[i + 1]) * (G[r + 1] - G[i]) - eps > (G[i] - G[i + 1]) * (G[r] - G[i])) r = (r + 1) % top;
H = fabs(cross(G[d] - G[i],G[i + 1] - G[i]) / D);
L = fabs((G[i + 1] - G[i]) * (G[l] - G[i + 1]) / D);
R = fabs((G[i + 1] - G[i]) * (G[r] - G[i]) / D);
//printf("(%.0lf,%.0lf) (%.0lf,%.0lf) ",G[i].x,G[i].y,G[i + 1].x,G[i + 1].y);
//printf("(%.0lf,%.0lf) (%.0lf,%.0lf) (%.0lf,%.0lf)",G[l].x,G[l].y,G[d].x,G[d].y,G[r].x,G[r].y);
//printf("D = %lf H = %lf\n",L + R + D,H);
double S = (L + R + D) * H;
if (S < ans){
ans = S;
t[0] = G[i + 1] + (G[i + 1] - G[i]) * (L / D);
t[1] = G[i] + (G[i] - G[i + 1]) * (R / D);
t[2] = t[1] + (G[r] - t[1]) * (H / dis(G[r],t[1]));
t[3] = t[0] + (G[l] - t[0]) * (H / dis(G[l],t[0]));
}
}
}
int main(){
scanf("%d",&n);
REP(i,n) scanf("%lf%lf",&p[i].x,&p[i].y);
graham();
//for (int i = 0; i <= top; i++) printf("(%lf,%lf)\n",G[i].x,G[i].y);
work();
if (fabs(ans) < eps) puts("0.00000");
else printf("%.5lf\n",ans);
int pos = 0;
for (int i = 1; i < 4; i++)
if (t[i].y < t[pos].y) pos = i;
for (int i = pos,j = 0; j < 4; i = (i + 1) % 4,j++){
if (fabs(t[i].x) < eps) printf("0.00000 ");
else printf("%.5lf ",t[i].x);
if (fabs(t[i].y) < eps) printf("0.00000\n");
else printf("%.5lf\n",t[i].y);
}
return 0;
}