uva 10625 Board Wrapping

https://vjudge.net/problem/UVA-10652

给出n个长方形，用一个面积尽量小的凸多边形把他们围起来

求木板占包装面积的百分比

输入给出长方形的中心坐标，长，宽，以及长方形顺时针旋转的角度

求凸包

处理输入：

长方形四个顶点的向量坐标=中心点的向量坐标+从中心出发的向量旋转长方形的旋转角度

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

const double pi=acos(-);

const double eps=1e-;

int dcmp(double x,double y)

{

    if(fabs(x-y)<eps) return ;

    return x<y ? - : ;

}

struct Point

{

    double x,y;

    Point(double x=,double y=):x(x),y(y) { }

};

typedef Point Vector;

Point P[],ch[];

Vector operator + (Vector A,Vector B) { return Vector(A.x+B.x,A.y+B.y); }

Vector operator - (Vector A,Vector B) { return Vector(A.x-B.x,A.y-B.y); }

double torad(double j)

{

    return j*pi/;

}

double Cross(Vector A,Vector B) { return A.x*B.y-A.y*B.x; }

Vector Rotate(Vector A,double rad)

{

    return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));

}

bool cmp(Point A,Point B)

{

    if(!dcmp(A.x,B.x)) return A.y<B.y;

    return A.x<B.x;

}

int ConvexHull(Point *p,int n,Point *c)

{

    sort(p,p+n,cmp);

    int m=;

    for(int i=;i<n;++i)

    {

        while(m> && Cross(c[m-]-c[m-],P[i]-c[m-])<=)

            m--;

        c[m++]=P[i];

    }

    int k=m;

    for(int i=n-;i>=;--i)

    {

        while(m>k && Cross(c[m-]-c[m-],P[i]-c[m-])<=) m--;

        c[m++]=P[i];

    }

    if(n>) m--;

    return m;

}

double PolygonArea(Point *p,int n)

{

    double area=;

    for(int i=;i<n-;++i) area+=Cross(p[i]-p[],p[i+]-p[]);

    return area/;

}

int main()

{

    int T,n,m,pc;

    double x,y,w,h,j,ang;

    double area1,area2;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        pc=;

        area1=;

        for(int i=;i<=n;++i)

        {

            scanf("%lf%lf%lf%lf%lf",&x,&y,&w,&h,&j);

            Point o(x,y);

            ang=-torad(j);

            P[pc++]=o+Rotate(Vector(-w/,-h/),ang);

            P[pc++]=o+Rotate(Vector(-w/,h/),ang);

            P[pc++]=o+Rotate(Vector(w/,-h/),ang);

            P[pc++]=o+Rotate(Vector(w/,h/),ang);

            area1+=w*h;

        }

        m=ConvexHull(P,pc,ch);

        area2=PolygonArea(ch,m);

        printf("%.1lf %%\n",area1*/area2);

    }

}