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;

}