UVa 10652 (简单凸包) Board Wrapping

浏览数：18 / 时间：2015年06月11日

题意：

有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个后面。

 1 //#define LOCAL
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cmath>
 6 #include <vector>
 7 using namespace std;
 8 
 9 const double PI = acos(-1.0);
10 
11 struct Point
12 {
13     double x, y;
14     Point(double x=0, double y=0):x(x), y(y){}
15 };
16 typedef Point Vector;
17 Point operator + (Vector A, Vector B) { return Vector(A.x+B.x, A.y+B.y); }
18 Point operator - (Vector A, Vector B) { return Vector(A.x-B.x, A.y-B.y); }
19 double Cross(const Vector& A, const Vector& B)      { return A.x*B.y - A.y*B.x; }
20 Vector Rotate(Vector A, double p)
21 {
22     return Vector(A.x*cos(p)-A.y*sin(p), A.x*sin(p)+A.y*cos(p));
23 }
24 bool operator < (const Point& A, const Point& B)
25 {
26     return A.x < B.x || (A.x == B.x && A.y < B.y);
27 }
28 bool operator == (const Vector& A, const Vector& B)
29 {
30     return A.x == B.x && A.y == B.y;
31 }
32 
33 double torad(double x) { return x / 180.0 * PI; }
34 
35 vector<Point> ConvexHull(vector<Point> p)
36 {
37     //Ô¤´¦Àí£¬È¥ÖØ 
38     sort(p.begin(), p.end());
39     p.erase(unique(p.begin(), p.end()), p.end());
40     
41     int n = p.size();
42     int m = 0;
43     vector<Point> ch(n+1);
44     for(int i = 0; i < n; ++i)
45     {
46         while(m > 1 && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;
47         ch[m++] = p[i];
48     }
49     int k = m;
50     for(int i = n-2; i >= 0; --i)
51     {
52         while(m > k && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;
53         ch[m++] = p[i];
54     }
55     if(n > 1)    m--;
56     ch.resize(m);
57     return ch;
58 }
59 
60 double PolygonArea(vector<Point> p)
61 {
62     int n = p.size();
63     double ans = 0.0;
64     for(int i = 0; i < n-1; ++i)
65             ans += Cross(p[i]-p[0], p[i+1]-p[0]);
66     return ans/2;
67 }
68 
69 int main(void)
70 {
71     #ifdef LOCAL
72         freopen("10652in.txt", "r", stdin);
73     #endif
74     
75     int T;
76     scanf("%d", &T);
77     while(T--)
78     {
79         int n;
80         vector<Point> p;
81         double area1 = 0.0;
82         scanf("%d", &n);
83         for(int i = 0; i < n; ++i)
84         {
85             double x, y, w, h, a;
86             scanf("%lf%lf%lf%lf%lf", &x, &y, &w, &h, &a);
87             Point o(x, y);
88             double ang = -torad(a);
89             p.push_back(o + Rotate(Vector(w/2, h/2), ang));
90             p.push_back(o + Rotate(Vector(-w/2, h/2), ang));
91             p.push_back(o + Rotate(Vector(w/2, -h/2), ang));
92             p.push_back(o + Rotate(Vector(-w/2, -h/2), ang));
93             area1 += w*h;
94         }
95         double area2 = PolygonArea(ConvexHull(p));
96         printf("%.1lf %%\n", area1 / area2 * 100.0);
97     }
98 }