UVA–10652 Board Wrapping[凸包] _Board

少年辛苦终身事，莫向光阴惰寸功。这篇文章主要讲述UVA– 10652 Board Wrapping[凸包]相关的知识，希望能为你提供帮助。
题意：给出n个矩形的中点、长、宽和顺时针的角度。让你用最小的凸多边形把他们包起来，计算矩形面积占凸多边形的百分比。用大白书给出的凸包的算法，将矩形的每个顶点都做一次凸包，求出凸包的面积。

文章图片

题意：
给出n个矩形的中点、长、宽和顺时针的角度。让你用最小的凸多边形把他们包起来，计算矩形面积占凸多边形的百分比。
【UVA– 10652 Board Wrapping[凸包]】用大白书给出的凸包的算法，将矩形的每个顶点都做一次凸包，求出凸包的面积。

#include "bits/stdc++.h" using namespace std; const int maxn = 3000; const double eps=1e-8; const double PI = acos(-1.0); struct Point { double x, y; Point(double x = 0.0, double y = 0.0):x(x), y(y) {} }; typedef Point Vector; Point operator + (Point A, Point B) { return Point(A.x+B.x, A.y+B.y); } Point operator - (Point A, Point B) { return Point(A.x-B.x, A.y-B.y); } Point operator * (Point A, double p) { return Point(A.x*p, A.y*p); } Point operator / (Point A, double p) { return Point(A.x/p, A.y/p); } bool operator < (const Point& a, const Point& b) { return a.x< b.x || (a.x==b.x & & a.y< b.y); } int dcmp(double x) { if (fabs(x)< eps) return 0; return x< 0?-1:1; } bool operator == (const Point& a, const Point & b) { return dcmp(a.x-b.x) == 0 & & dcmp(a.y-b.y)==0; } double Dot(Point A, Point B) { return A.x*B.x+A.y*B.y; } double Cross(Point A, Point B) { return A.x*B.y - A.y*B.x; } double Length(Point A) {return sqrt(Dot(A,A)); } Vector Normal(Vector A) {return Vector(-A.y, A.x)/Length(A); } double Angle(Vector A, Vector B) { return acos(Dot(A,B)/Length(A)/Length(B)); } Vector Rotate(Vector A, double rad) { return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad)); } double PolygonArea(Point* p, int n) { double area = 0.0; for (int i = 1; i < n-1; i++) area += Cross(p[i]-p[0],p[i+1]-p[0]); return area/2.0; } Point p[maxn], ch[maxn]; bool cmp(Point a, Point b) { if (dcmp(a.x - b.x) == 0) return dcmp(a.y - a.y) < = 0; return dcmp(a.x - b.x) < 0; } //输出n个点，输出ch作为凸包所含的点 //如果不希望边上有点将< =改为< 输入无重复点 int ConvexHull(Point* p, int n, Point* ch) { sort(p, p + n); //先比较x，在比较y字典序 int m = 0; for (int i = 0; i < n; i++) { while (m > 1 & & Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) < = 0) m--; ch[m++] = p[i]; } int k = m; for (int i = n - 2; i > = 0; i--) { while (m > k & & Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) < = 0) m--; ch[m++] = p[i]; } if (n > 1) m--; return m; } int main(int argc, char const *argv[]) { int T; scanf("%d", & T); while (T--) { int N, cnt = 0; scanf("%d", & N); double ara = 0.0; for (inti = 0; i < N; i++) { double x, y, w, h, j; scanf("%lf%lf%lf%lf%lf", & x, & y, & w, & h, & j); double ang = -(j/180.0)*PI; Point o = Point(x, y); p[cnt++] = o + Rotate(Vector(w/2, h/2), ang); p[cnt++] = o + Rotate(Vector(-w/2, h/2), ang); p[cnt++] = o + Rotate(Vector(w/2, -h/2), ang); p[cnt++] = o + Rotate(Vector(-w/2, -h/2), ang); ara += w*h; } int m = ConvexHull(p, cnt, ch); double A = PolygonArea(ch, m); printf("%.1lf %%\\n", ara*100/A); } return 0; }