2015年3月11日 星期三

UVA 10652 - Board Wrapping

模板題
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

const double PI = acos(-1);
const double eps = 1e-10;
int sgn(double a){ return a<-eps ? -1 : a>eps;}

class pt{
public:
    double x, y;
    pt(double _x = 0, double _y = 0):x(_x), y(_y){}
    pt rotate(double j){
        const double s = sin(j), c = cos(j);
        return pt(x*c-y*s,x*s+y*c);
    }    
};

bool operator==(const pt& a, const pt& b){return sgn(a.x-b.x) == 0 and sgn(a.y-b.y) == 0;}
pt operator-(const pt& a, const pt& b){return pt(a.x - b.x, a.y - b.y);}
pt operator+(const pt& a, const pt& b){return pt(a.x + b.x, a.y + b.y);}
double operator^(const pt& a, const pt& b){return a.x*b.y - a.y*b.x;}

struct cpbyx{bool operator()(pt a, pt b){return a.x == b.x ? a.y < b.y : a.x < b.x;}};
vector<pt> ConvexHull(vector<pt> inp){
    vector<pt> bt_ret, tp_ret;
    sort(inp.begin(), inp.end(), cpbyx());
    auto it = unique(inp.begin(), inp.end());
    inp.resize(distance(inp.begin(), it));
    for(int lx = 0;lx < inp.size();lx++){
        pt v = inp[lx];
        for(int ly = (int)bt_ret.size()-1;ly>=1;ly--){
            if(sgn((bt_ret[ly]-bt_ret[ly-1])^(v-bt_ret[ly])) <= 0){
                bt_ret.pop_back();
            }else
                break;
        }
        bt_ret.push_back(v);
    }
    for(int lx = (int)inp.size()-1;lx>=0;lx--){
        pt v = inp[lx];
        for(int ly = ((int)tp_ret.size())-1;ly>=1;ly--)
            if(sgn((tp_ret[ly]-tp_ret[ly-1])^(v-tp_ret[ly])) <= 0)
                tp_ret.pop_back();
            else
                break;
        tp_ret.push_back(v);
    }
    
    vector<pt> ret;
    for(int lx = 0;lx < bt_ret.size();lx++)
        ret.push_back(bt_ret[lx]);
    for(int lx = 0;lx < tp_ret.size();lx++)
        ret.push_back(tp_ret[lx]);
    return ret;
}

double CalArea(vector<pt> inp){
    double ret = 0;
    int len = inp.size();
    inp.push_back(inp[0]);
    for(int lx = 0;lx < len;lx++){
        ret += inp[lx]^inp[lx+1];
    }
    if(ret < 0) ret = -ret;
    return ret/2;
}

int main(){
    int T; scanf("%d", &T);
    while(T--){
        int n; scanf("%d", &n);
        vector<pt> get;
        double area1 = 0;
        for(int lx = 0;lx < n;lx++){
            double x, y, w, h, j;
            scanf("%lf %lf %lf %lf %lf", &x, &y, &w, &h, &j);
            area1 += w*h;
            double ang = -j*PI/180;
            get.push_back(pt(x, y) + pt(w/2, h/2).rotate(ang));
            get.push_back(pt(x, y) + pt(w/2, -h/2).rotate(ang));
            get.push_back(pt(x, y) + pt(-w/2, -h/2).rotate(ang));
            get.push_back(pt(x, y) + pt(-w/2, h/2).rotate(ang));
        }
        printf("%.1f %c\n",area1*100/CalArea(ConvexHull(get)), '%');
    }
    return 0;

}