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 integer n, 1< n <= 600, which is the number of boards in the mould. Then n lines follow, each with five floating point numbers x, y, w, h, j where 0 <= x, y, w, h <=10000 and –90° < j <=90°. The x and y are the coordinates of the center of the board and w 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 the x-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 given picture

题目大意：

给n个矩形木板，你要用一个面积尽量小的凸多边形把它们包起来，求木板占整个包装面积的百分比。

解题思路：

最主要还是求凸包。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const double eps=1e-7;
struct Point{
    double x,y;
    Point(double x0=0,double y0=0){
        x=x0,y=y0;
    }
    void read(){ scanf("%lf%lf",&x,&y); }
    friend bool operator < (Point a,Point b){
        if(a.y!=b.y) return a.y<b.y;
        else return a.x<b.x;
    }
    double getdis(Point q){ return sqrt( (x-q.x)*(x-q.x)+(y-q.y)*(y-q.y) ); }
};

typedef Point Vector;

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); }
Vector operator * (Vector A,double p) { return Vector(A.x*p,A.y*p); }
Vector operator / (Vector A,double p) { return Vector(A.x/p,A.y/p); }

int dcmp(double x) { if(fabs(x)<eps) return 0; else return x<0?-1:1; }
double Dot(Vector A,Vector B){ return A.x*B.x+A.y*B.y; }
double Length(Vector A){ return sqrt(Dot(A,A)); }
double Angle(Vector A,Vector B){ return acos(Dot(A,B)/Length(A)/Length(B)); }
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)); }//逆时针旋转rad角度
double torad(double ang){ return ang/180.0*acos(-1.0); }

const int maxn=2500;
Point p[maxn];
int n,top;
double sum;

bool cmp(Point a,Point b){
    if( fabs( Cross(a-p[0],b-a) )<eps ) return a.getdis(p[0])<b.getdis(p[0]);
    else return Cross(a-p[0],b-a)>0;
}

double ConvexHull(){
    top=1;
    sort(p,p+n);
    sort(p+1,p+n,cmp);
    for(int i=2;i<n;i++){
        while(top>0 && Cross(p[top]-p[top-1],p[i]-p[top-1])<=0) top--;
        p[++top]=p[i];
    }
    p[++top]=p[0];
    double area=0;
    for(int i=1;i<top;i++){
        area+=Cross(p[i]-p[0],p[i+1]-p[0]);
    }
    return area/2.0;
}

void input(){
    n=0;
    sum=0;
    int m;
    scanf("%d",&m);
    for(int i=0;i<m;i++){
        Point o;
        double w,h,ang,rad;
        scanf("%lf%lf%lf%lf%lf",&o.x,&o.y,&w,&h,&ang);
        rad=-torad(ang);
        p[n++]=o+Rotate(Vector(-w/2.0,-h/2.0),rad);
        p[n++]=o+Rotate(Vector(-w/2.0,h/2.0),rad);
        p[n++]=o+Rotate(Vector(w/2.0,h/2.0),rad);
        p[n++]=o+Rotate(Vector(w/2.0,-h/2.0),rad);
        sum+=w*h;
    }
}

void solve(){
    double ans=ConvexHull();
    printf("%.1lf %%\n",sum*100.0/ans);
}

int main(){
    int T;
    scanf("%d",&T);
    while(T-- >0){
        input();
        solve();
    }
    return 0;
}

uva 10652 Board Wrapping （计算几何-凸包）,布布扣,bubuko.com

uva 10652 Board Wrapping （计算几何-凸包）