uva 10652

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

思路：按照题意将所有矩形顶点坐标存起来，旋转时先旋转从中心出发的向量，求得各个坐标之后，求凸包即可。

水。。。。

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<memory.h>

 #include<cstdlib>

 #include<vector>

 #define clc(a,b) memset(a,b,sizeof(a))

 #define LL long long int

 #define up(i,x,y) for(i=x;i<=y;i++)

 #define w(a) while(a)

 using namespace std;

 const int inf=0x3f3f3f3f;

 const int N = ;

 const double eps = *1e-;

 const double pi = acos(-);

 const double PI = acos(-1.0);

 double torad(double deg)

 {

     return deg/ * PI;

 }

 struct Point

 {

     double x, y;

     Point(double x=, double y=):x(x),y(y) { }

 };

 typedef Point Vector;

 Vector operator + (const Vector& A, const Vector& B)

 {

     return Vector(A.x+B.x, A.y+B.y);

 }

 Vector operator - (const Point& A, const Point& B)

 {

     return Vector(A.x-B.x, A.y-B.y);

 }

 double Cross(const Vector& A, const Vector& B)

 {

     return A.x*B.y - A.y*B.x;

 }

 Vector Rotate(const Vector& A, double rad)

 {

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

 }

 bool operator < (const Point& p1, const Point& p2)

 {

     return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);

 }

 bool operator == (const Point& p1, const Point& p2)

 {

     return p1.x == p2.x && p1.y == p2.y;

 }

 // 点集凸包

 // 如果不希望在凸包的边上有输入点，把两个 <= 改成 <

 // 如果不介意点集被修改，可以改成传递引用

 vector<Point> ConvexHull(vector<Point> p)

 {

     // 预处理，删除重复点

     sort(p.begin(), p.end());

     p.erase(unique(p.begin(), p.end()), p.end());

     int n = p.size();

     int m = ;

     vector<Point> ch(n+);

     for(int i = ; i < n; i++)

     {

         while(m >  && Cross(ch[m-]-ch[m-], p[i]-ch[m-]) <= ) m--;

         ch[m++] = p[i];

     }

     int k = m;

     for(int i = n-; i >= ; i--)

     {

         while(m > k && Cross(ch[m-]-ch[m-], p[i]-ch[m-]) <= ) m--;

         ch[m++] = p[i];

     }

     if(n > ) m--;

     ch.resize(m);

     return ch;

 }

 // 多边形的有向面积

 double PolygonArea(vector<Point> p)

 {

     double area = ;

     int n = p.size();

     for(int i = ; i < n-; i++)

         area += Cross(p[i]-p[], p[i+]-p[]);

     return area/;

 }

 int main()

 {

     int T;

     scanf("%d", &T);

     while(T--)

     {

         int n;

         double area1 = ;

         scanf("%d", &n);

         vector<Point> P;

         for(int i = ; 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.push_back(o + Rotate(Vector(-w/,-h/), ang));

             P.push_back(o + Rotate(Vector(w/,-h/), ang));

             P.push_back(o + Rotate(Vector(-w/,h/), ang));

             P.push_back(o + Rotate(Vector(w/,h/), ang));

             area1 += w*h;

         }

         double area2 = PolygonArea(ConvexHull(P));

         printf("%.1lf %%\n", area1*/area2);

     }

     return ;

 }