要点
- 凸包显然
- 长方形旋转较好的处理方式就是用中点的Vector加上旋转的Vector,然后每个点都扔到凸包里
- 多边形面积板子求凸包面积即可
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef double db;
const db eps = 1e-9;
const db PI = acos(-1.0);
const int maxn = 600 * 4 + 5;
int T, n;
db x, y, w, h, j, S;
int dcmp(db x) {
if (fabs(x) < eps) return 0;
return x > 0 ? 1 : -1;
}
struct Vector {
db x, y;
Vector(){}
Vector(db a, db b):x(a), y(b){}
bool operator < (const Vector &rhs) const {
if (dcmp(x - rhs.x) != 0) return dcmp(x - rhs.x) < 0;
return dcmp(y - rhs.y) < 0;
}
};
Vector p[maxn], v[maxn];
int m, cnt;
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 Vector& A, const Vector& B) { return dcmp(A.x - B.x) == 0 && dcmp(A.y - B.y) == 0; }
db toRad(db ang) {//角度转弧度
return ang / 180 * PI;
}
Vector Rotate(Vector A, double rad) {//逆时针旋转
return Vector(A.x*cos(rad) - A.y*sin(rad), A.x*sin(rad) + A.y*cos(rad));
}
db Cross(Vector A, Vector B) {//叉积
return A.x * B.y - A.y * B.x;
}
db Polygon_Area(Vector *p, int n) {//多边形面积,逆时针取点0~n-1
db area = 0;
for (int i = 1; i < n - 1; i++)
area += Cross(p[i] - p[0], p[i + 1] - p[0]);
return area / 2;
}
void ConvexHull(int n) {
sort(p, p + n);
n = unique(p, p + n) - p;//去重
for (int i = 0; i < n; i++) {
while (cnt > 1 && dcmp(Cross(v[cnt - 1] - v[cnt - 2], p[i] - v[cnt - 2])) <= 0) cnt--;
v[cnt++] = p[i];
}
int k = cnt;
for (int i = n - 2; ~i; --i) {
while (cnt > k && dcmp(Cross(v[cnt - 1] - v[cnt - 2], p[i] - v[cnt - 2])) <= 0) cnt--;
v[cnt++] = p[i];
}
if (n > 1) cnt--;
}
int main() {
for (scanf("%d", &T); T--; m = cnt = 0, S = 0.0) {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%lf %lf %lf %lf %lf", &x, &y, &w, &h, &j);
Vector o(x, y);
db delta = toRad(j);//转弧度,注意顺时针
p[m++] = o + Rotate(Vector(w / 2, h / 2), -delta);
p[m++] = o + Rotate(Vector(w / 2, -h / 2), -delta);
p[m++] = o + Rotate(Vector(-w / 2, h / 2), -delta);
p[m++] = o + Rotate(Vector(-w / 2, -h / 2), -delta);
S += w * h;
}
ConvexHull(m);
db Sum = Polygon_Area(v, cnt);
printf("%.1lf %%\n", S / Sum * 100);
}
}