UVA - 10652

[Submit]   [Go Back]   [Status]  

Description

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°. Thex 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块矩形木板,你的任务是用一个面积尽量小的凸多边形把他们包围起来,并计算出木板占整个包装面积的百分比;

意解: 所用到的几何知识有基于水平序的andrew算法,向量的旋转和求多边形的面积等几何知识;

以下的向量旋转知识是拷贝别人的;   而对于多边形的面积求法则很自然;

在二维坐标系中，一个位置向量的旋转公式可以由三角函数的几何意义推出。

比如上图所示是位置向量R逆时针旋转角度B前后的情况。

      在左图中，我们有关系：

　　x0 = |R| * cosA       =>          cosA = x0 / |R|

　　y0 = |R| * sinA        =>          sinA = y0 / |R|

  　在右图中，我们有关系：

　　x1 = |R| * cos（A+B）

　　y1 = |R| * sin（A+B）

　　其中（x1， y1）就是（x0， y0）旋转角B后得到的点，也就是位置向量R最后指向的点。我们展开cos（A+B）和sin（A+B），得到：

　　x1 = |R| * （cosAcosB - sinAsinB）

　　y1 = |R| * （sinAcosB + cosAsinB）

　　现在把  cosA = x0 / |R| 和 sinA = y0 / |R|  代入上面的式子，得到：

　　x1 = |R| * （x0 * cosB / |R| - y0 * sinB / |R|） =>  x1 = x0 * cosB - y0 * sinB

　　y1 = |R| * （y0 * cosB / |R| + x0 * sinB / |R|） =>  y1 = x0 * sinB + y0 * cosB

　　这样我们就得到了二维坐标下向量围绕圆点的逆时针旋转公式。顺时针旋转就把角度变为负：

　　x1 = x0 * cos（-B） - y0 * sin（-B） =>  x1 = x0 * cosB + y0 * sinB

　　y1 = x0 * sin（-B） + y0 * cos（-B）=>  y1 = -x0 * sinB + y0 * cosB

　　现在我要把这个旋转公式写成矩阵的形式，有一个概念我简单提一下，平面或空间里的每个线性变换（这里就是旋转变换）都对应一个矩阵，叫做变换矩阵。对一个点实施线性变换就是通过乘上该线性变换的矩阵完成的。好了，打住，不然就跑题了。

所以二维旋转变换矩阵就是：

                                           [cosA  sinA]          [cosA -sinA]
                                           [-sinA cosA] 或者  [sinA cosA]

　　我们对向量进行旋转变换可以通过矩阵完成，比如我要向量（x， y）绕原点逆时针旋转角度A：

                      [x, y] x  [cosA  sinA]     = [x*cosA-y*sinA  x*sinA+y*cosA]       

                                  [-sinA cosA]

AC代码:

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#define pi acos(-1.0)
#define exp 1e-10

using namespace std;

struct  Point
{
    double x,y;
    Point(double x0 = 0, double y0 = 0) //构造函数,初始化;
    {
        x = x0;
        y = y0;
    }
    bool operator < (const Point &ant) const //求凸包时需要对x和y排序,注意点不能有重复,有的话要去重;
    {
        if(ant.x != x) return ant.x > x;
        return ant.y > y;
    }
};

typedef Point Vector;

Vector operator + (Vector A, Vector B) //自定义重载+运算;
{
    return Vector(A.x + B.x, B.y + A.y);
}

Vector operator - (Vector A, Vector B) //自定义重载-运算;
{
    return Vector(A.x - B.x, A.y - B.y);
}

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

double change(double j) //转化为弧度制
{
    return j / 180.0 * pi;
}

double cross(Vector A, Vector B) //向量的叉积
{
    return A.x * B.y - A.y * B.x;
}

class Convex
{
public:
    int convex(Vector *p, int n, Vector *ch) //求凸包
    {
        sort(p,p + n);
        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]) <= exp) 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]) <= exp) m--;
            ch[m++] = p[i];
        }
        if(n > 1) m--;
        return m;
    }

    double PolygonArea(Point *p, int n)//求多边形的面积
    {
        double area2 = 0.0;
        for(int i = 1; i < n - 1; i++)
        {
            area2 += cross(p[i] - p[0], p[i + 1] - p[0]);
        }
        return 0.5 * fabs(area2);
    }

} hull;

int main()
{
    int T;
    Point p[2500],ch[2500];
    scanf("%d",&T);
    while(T--)
    {
        int n,pc = 0;
        double area1 = 0.0;
        scanf("%d",&n);
        for(int i = 0; i < n; i++)
        {
            double w,h,j,rad;
            Point o;
            scanf("%lf %lf %lf %lf %lf",&o.x, &o.y, &w,&h,&j);
            rad = -change(j);
            p[pc++] = o + Rotate(Vector(-w/2,-h/2),rad);//求出木板的四个定点的坐标
            p[pc++] = o + Rotate(Vector( w/2,-h/2),rad);
            p[pc++] = o + Rotate(Vector(-w/2, h/2),rad);
            p[pc++] = o + Rotate(Vector( w/2, h/2),rad);
            area1 += w * h;//累积木板的面积
        }
        int m = hull.convex(p,pc,ch); //求凸包;
        double area2 = hull.PolygonArea(ch,m); //求面积
        printf("%.1lf %%\n", area1 * 100 / area2);
    }
    return 0;
}