嗯，毒瘤题。
首先有一个结论，就是最小矩形一定有条边和凸包重合。脑补一下就好了。
然后枚举凸包的边，用旋转卡壳维护上顶点、左端点、右端点就好了。
上顶点用叉积，叉积越大三角形面积越大，对应的高也就越大。两边的点用点积，点积越大投影越大。
然后就是精度问题。这种实数计算最好不要直接用比较运算符，要用差和
\(eps\)的关系来比较，我就是一直卡在这里。还好有爆炸
\(OJ\)离线题库提供的数据。。。
#include #include #include using namespace std;const int MAXN = 50010;const double eps = 1e-8;struct point{ double x, y; inline double dis(){ return sqrt(x * x + y * y); } inline void print(){ if(fabs(x) < 1e-10) x = 0; if(fabs(y) < 1e-10) y = 0; printf("%.5lf %.5lf\n", x, y); }}p[MAXN];inline double sig(double x){ return (x > eps) - (x < -eps);}int operator == (point a, point b){ return a.x == b.x && a.y == b.y;}point operator * (point a, double b){ // ba return (point){ a.x * b, a.y * b };}double operator * (point a, point b){ // a x b return a.x * b.y - b.x * a.y;}double operator / (point a, point b){ // a . b return a.x * b.x + a.y * b.y;}point operator - (point a, point b){ // a - b return (point){ a.x - b.x, a.y - b.y };}point operator + (point a, point b){ // a + b return (point){ a.x + b.x, a.y + b.y };}int cmp(const point a, const point b){ return a.x == b.x ? a.y < b.y : a.x < b.x;}inline int judge(point a, point b, point c){ //Kab > Kac return (b.y - a.y) * (c.x - a.x) > (c.y - a.y) * (b.x - a.x); }inline double mult(point a, point b, point c){ return (a - c) * (b - c);}inline double calc(point a, point b, point c){ return (b - a) / (c - a);}int n, top, tp;point st[MAXN], ts[MAXN], Ans[5];double ans = 1e18, d, a, b, L, R;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 + n + 1, cmp); for(int i = 1; i <= n; ++i){ if(p[i] == p[i - 1]) continue; while(top > 1 && judge(st[top - 1], st[top], p[i])) --top; st[++top] = p[i]; } for(int i = 1; i <= n; ++i){ if(p[i] == p[i - 1]) continue; while(tp > 1 && !judge(ts[tp - 1], ts[tp], p[i])) --tp; ts[++tp] = p[i]; } for(int i = tp - 1; i; --i) st[++top] = ts[i]; --top; int j = 2, k = 2, l = 2; for(int i = 1; i <= top; ++i){ while(sig(mult(st[i], st[i + 1], st[j]) - mult(st[i], st[i + 1], st[j + 1])) <= 0) if(++j > top) j = 1; while(sig(calc(st[i], st[i + 1], st[k]) - calc(st[i], st[i + 1], st[k + 1])) <= 0) if(++k > top) k = 1; if(i == 1) l = k; while(sig(calc(st[i], st[i + 1], st[l]) - calc(st[i], st[i + 1], st[l + 1])) >= 0) if(++l > top) l = 1; d = (st[i] - st[i + 1]).dis(); R = calc(st[i], st[i + 1], st[k]) / d; L = calc(st[i], st[i + 1], st[l]) / d; b = fabs(mult(st[i], st[i + 1], st[j]) / d); a = R - L; if(a * b < ans){ ans = a * b; Ans[1] = st[i] + (st[i + 1] - st[i]) * (R / d); Ans[2] = Ans[1] + (st[k] - Ans[1]) * (b / (st[k] - Ans[1]).dis()); Ans[3] = Ans[2] + (st[i] - Ans[1]) * (a / R); Ans[4] = Ans[3] + (Ans[1] - Ans[2]); } } printf("%.5lf\n", ans); double Min = 1e18, pos; for(int i = 1; i <= 4; ++i) if(Ans[i].y < Min) Min = Ans[i].y, pos = i; for(int i = pos; i <= 4; ++i) Ans[i].print(); for(int i = 1; i < pos; ++i) Ans[i].print(); return 0;}