題意：

有n塊互不重疊的矩形木板，用盡量小的凸多邊形將它們包起來，并輸出并輸出木板總面積占凸多邊形面積的百分比。

分析：

幾乎是凸包和多邊形面積的裸題。

?

注意：最后輸出的百分號前面有個空格，第一次交PE了。

用printf打印%，可以連續(xù)打印兩個%%，printf("%%\n");?? 這個冷知識記得以前學(xué)過，不過不用也就忘了。

學(xué)習(xí)一下vector容器中去重的小技巧。

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

?

ConvexHull函數(shù)最后用到了resize(n)，顧名思義就是改變?nèi)萜鞯拇笮閚。超過該范圍的元素?zé)o效，下次push_back進(jìn)來的元素將在第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 } 代碼君

?

轉(zhuǎn)載于:https://www.cnblogs.com/AOQNRMGYXLMV/p/4033252.html

總結(jié)

以上是生活随笔為你收集整理的UVa 10652 (简单凸包) Board Wrapping的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。