点击打开链接

Problem B

Board Wrapping

Input: standard input
Output: standard output

Time Limit: 2 seconds

The small sawmill in Mission, British Columbia, has developed a brand new way of packaging boards for drying. By fixating the boards in special moulds, the board can dry efficiently in a drying room.

Space is an issue though. The boards cannot be too close, because then the drying will be too slow. On the other hand, one wants to use the drying room efficiently.

Looking at it from a 2-D perspective, your task is to calculate the fraction between the space occupied by the boards to the total space occupied by the mould. Now, the mould is surrounded by an aluminium frame of negligible thickness, following
the hull of the boards' corners tightly. The space occupied by the mould would thus be the interior of the frame.

Input

On the first line of input there is one integer, N< = 50, giving the number of test cases (moulds) in the input. After this line,N test cases follow. Each test case starts with a line containing one integern,
1< n <= 600, which is the number of boards in the mould. Thenn lines follow, each with five floating point numbers
x, y, w, h, j where0 <= x, y, w, h <=10000 and
–90° <j< =90°. The x and y are the coordinates of the center of the board andw and
h are the width and height of the board, respectively.j is the angle between the height axis of the board to the
y-axis in degrees, positive clockwise. That is, if j = 0, the projection of the board on thex-axis would be
w. Of course, the boards cannot intersect.

Output

For every test case, output one line containing the fraction of the space occupied by the boards to the total space in percent. Your output should have one decimal digit and be followed by a space and a percent sign (%).

Sample Input                              Output for Sample Input

Swedish National Contest

The Sample Input and Sample Output corresponds to the
givenpicture

有n块矩形木板，你的任务是用一个面积尽量小的凸多边形把它们包起来，并计算出木板占整个包装面积的百分比。

凸包问题，求出凸包的面积和各个矩形的面积即可。

#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
struct Point
{
    double x,y;
    Point(double x=0,double y=0):x(x),y(y) {} //构造函数
};
typedef Point Vector;
const double pi = acos(-1);

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

//点-点=向量
Point operator-(Point A,Point B)
{
    return Point(A.x-B.x,A.y-B.y);
}


//向量*数=向量
Point operator*(Point A,double p)
{
    return Point(A.x*p,A.y*p);
}


//向量/数=向量
Point operator/(Point A,double p)
{
    return Point(A.x/p,A.y/p);
}

double torad(double x)//将度转为弧度
{
    return x*pi/180;
}
double Cross(Point A,Point B)
{
    return A.x*B.y-A.y*B.x;
}

//向量的旋转
Point Rotate(Point A,double rad)//rad是弧度
{
    return Point(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
}
double PolygonArea(Point* p,int n)//p是一个结构体数组
{
    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 cmp(const Point &a,const Point &b)
{
    if(a.x==b.x)return a.y<b.y;
    return a.x<b.x;
}
int ConvexHull(Point* p,int n,Point* ch)//求凸包
{
    sort(p,p+n,cmp);
    int m=0;
    for(int i=0;i<n;i++)
    {
        while(m>1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;
        ch[m++]=p[i];
    }
    int k=m;
    for(int i=n-2;i>=0;i--)
    {
        while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;
        ch[m++]=p[i];
    }
    if(n>1)m--;
    return m;
}
int main()
{
    int t;
    Point P[2500],ch[2500];
    scanf("%d",&t);
    while(t--)
    {
        int n,pc=0;
        double area1=0;
        scanf("%d",&n);
        for(int i=0; i<n; i++)
        {
            double x,y,w,h,j,ang;
            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;
        }
        int m=ConvexHull(P,pc,ch);
        double area2=PolygonArea(ch,m);
        printf("%.1lf %%\n",area1*100/area2);
    }
    return 0;
}

凸包模板：

输入点数组p，个数p，输出点数组ch。返回凸包顶点数。

int cmp(const Point &a,const Point &b)
{
    if(a.x==b.x)return a.y<b.y;
    return a.x<b.x;
}
int ConvexHull(Point *p,int n,Point *ch)//ch是空的
{
    sort(p,p+n);//x按照从小到大排序，若x相等，按照y从小到大排序
    n=unique(p,p+n)-p;//防止重边
    int m=0;
    for(int i=0;i<n;i++)
    {
        while(m>1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;
        ch[m++]=p[i];
    }
    int k=m;
    for(int i=n-2;i>=0;i--)
    {
        while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;
        ch[m++]=p[i];
    }
    if(n>1)m--;
    return m;//返回的是凸包的顶点数，ch数组存的是凸包的顶点
}