uva 10625 Board Wrapping

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

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

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

求凸包

处理输入：

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

#include<cstdio>
#include<cmath>
#include<algorithm>

using namespace std;

const double pi=acos(-1);

const double eps=1e-10;

int dcmp(double x,double y)
{
    if(fabs(x-y)<eps) return 0;
    return x<y ? -1 : 1;
}

struct Point
{
    double x,y;
    
    Point(double x=0,double y=0):x(x),y(y) { } 
    
};

typedef Point Vector;

Point P[2401],ch[2401]; 

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/180;
}

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=0;
    for(int i=0;i<n;++i)
    {
        while(m>1 && Cross(c[m-1]-c[m-2],P[i]-c[m-2])<=0) 
            m--;
        c[m++]=P[i];
    }
    int k=m;
    for(int i=n-2;i>=0;--i)
    {
        while(m>k && Cross(c[m-1]-c[m-2],P[i]-c[m-2])<=0) m--;
        c[m++]=P[i];
    }
    if(n>1) m--;
    return m;
}

double PolygonArea(Point *p,int n)
{
    double area=0;
    for(int i=1;i<n-1;++i) area+=Cross(p[i]-p[0],p[i+1]-p[0]);
    return area/2;
}

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=0;
        area1=0;
        for(int i=1;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/2,-h/2),ang);
            P[pc++]=o+Rotate(Vector(-w/2,h/2),ang);
            P[pc++]=o+Rotate(Vector(w/2,-h/2),ang);
            P[pc++]=o+Rotate(Vector(w/2,h/2),ang);
            area1+=w*h;
        }
        m=ConvexHull(P,pc,ch);
        area2=PolygonArea(ch,m);
        printf("%.1lf %%
",area1*100/area2);
    } 
}