旋转卡壳 90pts 求助（方案不合法）

8
0.99999 0.00003
1.00003 0.00001
0.00001 2.99997
0.00003 3.00001
2.99997 3.99999
3.00001 3.99997
3.99997 0.99999
3.99999 1.00003

#include <bits/stdc++.h>

using namespace std;

typedef long double db;

constexpr db eps=1e-18; constexpr int MAXN=5e4+10;

#define eq(x,y) (fabs((x)-(y))<=eps)
db pi=acosl(-1);
struct point {
    db x, y;
    point() {}
    point(db x, db y): x(x), y(y) {}
};

bool operator==(point a, point b) {
    return eq(a.x,b.x)&&eq(a.y,b.y);
}

typedef point vec;

vec operator+(vec a, vec b) { return {a.x+b.x,a.y+b.y}; }
vec operator-(vec a, vec b) { return {a.x-b.x,a.y-b.y}; }
vec operator*(db k, vec a) { return {k*a.x,k*a.y}; }
db operator*(vec a, vec b) { return a.x*b.x+a.y*b.y; }
db operator^(vec a, vec b) { return a.x*b.y-a.y*b.x; }
db len(vec a) { return sqrtl(a*a); }
db dist(point a, point b) { return len(a-b); }
vec norm(vec a) { return (1/len(a))*a; }
vec rotate(vec a, db ang) {
    return {a.x*cos(ang)-a.y*sin(ang),
    a.x*sin(ang)+a.y*cos(ang)};
}

bool check(point p, point q, point r) {
    return ((q-p)^(r-q))<eps;
}

struct line {
    point p; vec v;
    line() {}
    line(point A, point B) {
        p=A, v=B-A;
    }
};
line makeline(point a, vec b) {
    line l; l.p=a, l.v=b;
    return l;
}
point cross(line a, line b) {
    auto u=a.v, v=b.v, w=a.p-b.p;
    return a.p+((v^w)/(u^v))*u;
}

typedef vector<point> points;
point o;

db angle(point p) {
    if (p==o) return -1/.0;
    return atan2(p.y-o.y,p.x-o.x);
}

points convex_hull(points& a) {
    points p; 
    sort(a.begin(),a.end(),[](point a, point b) {
        if (eq(a.x,b.x)) return a.y<b.y;
        return a.x<b.x;
    });
    o=a[0];
    sort(a.begin(),a.end(),[](point a, point b) {
        db a1=angle(a), a2=angle(b);
        if (eq(a1,a2)) return dist(a,o)<dist(b,o);
        return a1<a2;
    });
    p.push_back(a[0]);
    for (int i=1; i<a.size(); ++i) {
        while (p.size()>1 && check(p[p.size()-2],p.back(),a[i])) p.pop_back();
        p.push_back(a[i]);
    }
    return move(p);
}

db sqr(point a, point b, point c) {
    return fabs((a-b)^(b-c));
}

db maxarea(points& p, points& rec) {
    int n=p.size();
    db ans=1e9; p.push_back(p[0]); 
    int j=1, l=1, r=1;
    for (int i=0; i<n; ++i) {
        while (sqr(p[i],p[i+1],p[j])<
            sqr(p[i],p[i+1],p[(j+1)%n])) j=(j+1)%n;
        while ((p[i+1]-p[i])*p[r]<(p[i+1]-p[i])*p[(r+1)%n]) r=(r+1)%n;
        if (!i) l=r;
        while ((p[i]-p[i+1])*p[l]<(p[i]-p[i+1])*p[(l+1)%n]) l=(l+1)%n;
        db h=sqr(p[i],p[i+1],p[j])/dist(p[i],p[i+1]), 
            w=dist(p[i],p[i+1])+
            fabs(norm(p[i]-p[i+1])*(p[i+1]-p[r]))+
            fabs(norm(p[i+1]-p[i])*(p[i]-p[l]));
        if (w*h<ans) {
            ans=w*h; rec.clear();
            line h1=makeline(p[i],p[i+1]-p[i]);
            line h2=makeline(p[j],p[i+1]-p[i]);
            vec u=rotate(p[i+1]-p[i],pi/2);
            line v1=makeline(p[l],u),
                v2=makeline(p[r],u);
            rec.push_back(cross(h1,v1));
            rec.push_back(cross(h2,v2));
            rec.push_back(cross(h2,v1));
            rec.push_back(cross(h1,v2));
        }
    }
    sort(rec.begin(),rec.end(),[](point a, point b) {
        if (eq(angle(a),angle(b))) return len(a)<len(b);
        return angle(a)<angle(b);
    });
    return ans;
}
int n; points a, p, rec;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    point t; cin>>n;
    for (int i=1; i<=n; ++i) cin>>t.x>>t.y, a.push_back(t);
    p=convex_hull(a);
    o={0,0};
    cout<<setiosflags(ios::fixed)<<setprecision(5)<<maxarea(p,rec)<<'\n';
    
    for (auto [x,y]: rec) {
        cout<<x+eps<<' ';
        cout<<y+eps<<'\n';
    }
}