Uva 10652 Board Wrapping

与天地兮比寿，与日月兮齐光。这篇文章主要讲述Uva 10652 Board Wrapping相关的知识，希望能为你提供帮助。
二次联通门 : Virtual Judge Uva 10652 Board Wrapping

/* Uva 10652 Board Wrapping计算几何将每个家具拆为4个点对所有点求一个凸包然后求凸包的面积即可思路不难。。但是写起来好麻烦好麻烦需要注意的东西有很多1. 角度制转弧度制 2. EPS的选择 3. PI的取值 (以防万一以后还是都写acos(-1)吧。。。) 4. 在把家具拆成四个点时的细节 4. 计算多边形的面积 */ #include < algorithm> #include < iostream> #include < cstdio> #include < cmath> #define Max 2500#define PI 3.1415926535897#define EPS 1e-8void read (int & now) { register char word = getchar (); for (now = 0; !isdigit (word); word = getchar ()); for (; isdigit (word); now = now * 10 + word - ‘0‘, word = getchar ()); }struct Point { double x, y; Point (const double & __x, const double & __y) : x (__x), y (__y) {} Point () {}bool operator < (const Point & now) const { return this-> x == now.x ? this-> y < now.y : this-> x < now.x; }bool operator == (const Point & now) const { return (this-> x - now.x < EPS) & & (this-> y - now.y < EPS); } }; typedef Point Vector; Vector operator + (const Vector & A, const Vector & B) { return Vector (A.x + B.x, A.y + B.y); }Vector operator - (const Vector & A, const Vector & B) { return Vector (A.x - B.x, A.y - B.y); }Vector operator * (const Vector & now, const double P) { return Vector (now.x * P, now.y * P); }Vector operator / (const Vector & now, const double P) { return Vector (now.x / P, now.y / P); }inline double to_rad (double now) { return now / 180 * PI; }inline Vector Rotate (Vector A, double rad) { return Vector (A.x * cos (rad) - A.y * sin (rad), A.x * sin (rad) + A.y * cos (rad)); }inline double Cross (Vector A, Vector B) { return A.x * B.y - A.y * B.x; }int Convex_Hull (Point *point, int N, Point *Stack) { std :: sort (point, point + N); int top = 0; for (int i = 0; i < N; i ++) { for (; top > 1 & & Cross (Stack[top - 1] - Stack[top - 2], point[i] - Stack[top - 2]) < = 0; -- top); Stack[top ++] = point[i]; }int k = top; for (int i = N - 2; i > = 0; -- i) { for (; top > k & & Cross (Stack[top - 1] - Stack[top - 2], point[i] - Stack[top - 2]) < = 0; -- top); Stack[top ++] = point[i]; } if (N > 1) -- top; return top; }double Polygon_Area (Point *point, int N) { double area = 0; for (int i = 1; i < N - 1; i ++) area += Cross (point[i] - point[0], point[i + 1] - point[0]); return area / 2; }Point point[Max], Stack[Max]; int main (int argc, char *argv[]) { int T, N, M; read (T); register int i; double x, y, w, h, j; double angle, _area; int cur; for (; T; -- T) { read (N); cur = 0, _area = 0; for (i = 1; i < = N; ++ i) { scanf ("%lf%lf%lf%lf%lf", & x, & y, & w, & h, & j); Point now (x, y); angle = -to_rad (j); point[cur ++] = now + Rotate (Vector (-w / 2, -h / 2), angle); point[cur ++] = now + Rotate (Vector (w / 2, -h / 2), angle); point[cur ++] = now + Rotate (Vector (-w / 2, h / 2), angle); point[cur ++] = now + Rotate (Vector (w / 2, h / 2), angle); _area += w * h; }M = Convex_Hull (point, cur, Stack); double __area = Polygon_Area (Stack, M); printf ("%.1lf %%\n", _area * 100 / __area); } return 0; }

【Uva 10652 Board Wrapping】