也未经过题目测试。。。。

//AB X AC
double cross(Point A,Point B,Point C)
{
    return (B-A)^(C-A);
}

//AB*AC
double dot(Point A,Point B,Point C)
{
    return (B-A)*(C-A);
}

//最小矩形面积覆盖
// A 必须是凸包 (而且是逆时针顺序)
double min_rectangle_cover(polygon A)
{
    //特判A.n<3的情况
    if(A.n<3) return 0.0;
    A.p[A.n]=A.p[0];
    double ans=-1;
    int r=1,p=1,q;
    for(int i=0;i<A.n;i++)
    {
        //卡出离边 A.p[i] - A.p[i+1] 最远的点
        while(sgn(cross(A.p[i],A.p[i+1],A.p[r+1])-cross(A.p[i],A.p[i+1],A.p[r]))>=0)
            r=(r+1)%A.n;

        //卡出 A.p[i] - A.p[i+1] 方向上正向 n 最远的点
        while(sgn(dot(A.p[i],A.p[i+1],A.p[p+1])-dot(A.p[i],A.p[i+1],A.p[p]))>=0)
            p=(p+1)%A.n;

        if(i==0) q=p;

        //卡出 A.p[i] - A.p[i+1] 方向上负向最远的点
        while(sgn(dot(A.p[i],A.p[i+1],A.p[q+1])-dot(A.p[i],A.p[i+1],A.p[q]))<=0)
            q=(q+1)%A.n;
        double d=(A.p[i]-A.p[i+1]).len2();
        double tmp=cross(A.p[i],A.p[i+1],A.p[r])*(dot(A.p[i],A.p[i+1],A.p[p])-dot(A.p[i],A.p[i+1],A.p[q]))/d;
        if(ans<0||ans>tmp) ans=tmp;
    }
    return ans;
}

//直线切凸多边形
//多边形是逆时针的，在 q1q2 的左侧
vector<Point> convex_cut_line(const vector<Point> &ps,Point q1,Point q2)
{
    vector<Point>qs;
    int n=ps.size();
    for(int i=0;i<n;i++)
    {
        Point p1=ps[i],p2=ps[(i+1)%n];
        int d1=sgn((q2-q1)^(p1-q1)),d2=sgn((q2-q1)^(p2-q1));
        if(d1>=0) qs.push_back(p1);
        if(d1*d2<0)
            qs.push_back(Line(p1,p2).cross_point(Line(q1,q2)));
    }
    return qs;
}