首页 > 代码库 > UVa 10652 (简单凸包) Board Wrapping
UVa 10652 (简单凸包) Board Wrapping
题意：
有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 Point12 {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 LOCAL72 freopen("10652in.txt", "r", stdin);73 #endif74 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 }
UVa 10652 (简单凸包) Board Wrapping
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。