题意：
有n块互不重叠的矩形木板，用尽量小的凸多边形将它们包起来，并输出并输出木板总面积占凸多边形面积的百分比。
分析：
几乎是凸包和多边形面积的裸题。
注意：最后输出的百分号前面有个空格，第一次交PE了。
用printf打印%，可以连续打印两个%%，printf("%%\n"); 这个冷知识记得以前学过，不过不用也就忘了。
学习一下vector容器中去重的小技巧。
sort(p.begin(), p.end());
p.erase(unique(p.begin(), p.end()), p.end());
ConvexHull函数最后用到了resize(n)，顾名思义就是改变容器的大小为n。超过该范围的元素无效，下次push_back进来的元素将在第n个后面。
//#define LOCAL
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std; const double PI = acos(-1.0); struct Point
{
double x, y;
Point(double x=, double y=):x(x), y(y){}
};
typedef Point Vector;
Point operator + (Vector A, Vector B) { return Vector(A.x+B.x, A.y+B.y); }
Point operator - (Vector A, Vector 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(Vector A, double p)
{
return Vector(A.x*cos(p)-A.y*sin(p), A.x*sin(p)+A.y*cos(p));
}
bool operator < (const Point& A, const Point& B)
{
return A.x < B.x || (A.x == B.x && A.y < B.y);
}
bool operator == (const Vector& A, const Vector& B)
{
return A.x == B.x && A.y == B.y;
} double torad(double x) { return x / 180.0 * PI; } 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)
{
int n = p.size();
double ans = 0.0;
for(int i = ; i < n-; ++i)
ans += Cross(p[i]-p[], p[i+]-p[]);
return ans/;
} int main(void)
{
#ifdef LOCAL
freopen("10652in.txt", "r", stdin);
#endif int T;
scanf("%d", &T);
while(T--)
{
int n;
vector<Point> p;
double area1 = 0.0;
scanf("%d", &n);
for(int i = ; i < n; ++i)
{
double x, y, w, h, a;
scanf("%lf%lf%lf%lf%lf", &x, &y, &w, &h, &a);
Point o(x, y);
double ang = -torad(a);
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 * 100.0);
}
}
代码君