UVA–10652 Board Wrapping[凸包]

 

题意：

给出n个矩形的中点、长、宽和顺时针的角度。让你用最小的凸多边形把他们包起来，计算矩形面积占凸多边形的百分比。

用大白书给出的凸包的算法，将矩形的每个顶点都做一次凸包，求出凸包的面积。

#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 (int  i = 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 %%
", ara*100/A);
    }
    return 0;
}