UVA 10652 - Board Wrapping（二維凸包）

題目連結：點選打開連結

思路：求面積最小的凸多邊形把所有箱子圍起來， 這不就是凸包的定義嗎。 模闆題。

細節參見代碼：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <bitset>
#include <cstdlib>
#include <cmath>
#include <set>
#include <list>
#include <deque>
#include <map>
#include <queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef long double ld;
const double eps = 1e-10;
const double PI = acos(-1);
const int mod = 1000000000 + 7;
const int INF = 0x3f3f3f3f;
const int seed = 131;
const ll INF64 = ll(1e18);
const int maxn = 2500;
int T,n,m;
struct point {
    double x, y;
    point(double x=0, double y=0):x(x), y(y) {}
} p[maxn], ch[maxn];
typedef point Vector;
Vector operator + (Vector A, Vector B) { return Vector(A.x+B.x, A.y+B.y); }
Vector operator - (Vector A, Vector B) { return Vector(A.x-B.x, A.y-B.y); }
Vector operator * (Vector A, double p) { return Vector(A.x*p, A.y*p); }
Vector operator / (Vector A, double p) { return Vector(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;
    else 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 cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; }
double torad(double deg) {
    return deg / 180 * PI;
}
double area(point* p, int n) {
    double area = 0;
    for(int i = 1; i < n-1; i++) {
        area += cross(p[i]-p[0], p[i+1]-p[0]);
    }
    return area / 2;
}
int convexhull(point* p, int n, point* ch) {
    sort(p, p+n);
    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;
}
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 x, y, w, h, j, ang;
int main() {
    scanf("%d",&T);
    while(T--) {
        int pc = 0;
        double area1 = 0;
        scanf("%d",&n);
        for(int i = 0; i < n; i++) {
            scanf("%lf%lf%lf%lf%lf", &x, &y, &w, &h, &j);
            point o(x, y);
            ang = -torad(j);
            p[pc++] = o + Rotate(Vector(-w/2, -h/2), ang);
            p[pc++] = o + Rotate(Vector(w/2, -h/2), ang);
            p[pc++] = o + Rotate(Vector(-w/2, h/2), ang);
            p[pc++] = o + Rotate(Vector(w/2, h/2), ang);
            area1 += w * h;
        }
        int m = convexhull(p, pc, ch);
        double area2 = area(ch, m);
        printf("%.1f %%\n", area1 * 100 / area2);
    }
    return 0;
}