UVa 10652 - Board Wrapping

好久沒寫凸包了,寫起來好陌生

這題我有用到旋轉矩陣,不過學校還沒教到…
趁著數學課花了一點時間翻一下講義
幸好不難懂,寫起來也順順的
就順手把這題 AC 掉了

Description

座標平面上有許多矩形
每個矩形用其中心的 x, y 座標以及長寬還有其高與 y 軸夾角角度 (順時鐘為正) 表示
今以一繩緊密圍住所有矩形
求矩形面積和佔圍出圖形之百分比

Solution

凸包裸題
只要把矩形的四個點都算出來,求個凸包面積就完成了

那麼要如何求出矩形的四個點呢?
只要把以矩形中心為起點,四個頂點為終點的四個向量都旋轉給定之角度就可以了
這時候就需要用到旋轉矩陣了 (Line 18 ~ 20)

接下來直接求凸包面積就可以了
這裡我用的方法是測量師公式 (Line 86 ~ 97)

基本上這題只是模板題配上數學而已
沒有什麼難度(?

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(0);cin.tie(0)
#define endl '\n'
#define PI acos(-1.0)

using namespace std;

struct Point {
double x, y;
Point(double _x = 0.0, double _y = 0.0):
x(_x), y(_y) {}
Point operator + (const Point rhs) const {
return Point(x + rhs.x, y + rhs.y);
}
bool operator < (const Point rhs) const {
return x < rhs.x;
}
Point Rotate(double rad) {
return Point(x * cos(rad) - y * sin(rad), x * sin(rad) + y * cos(rad));
}
};

int N, n;
double x, y, w, h, ang, rad, area;
vector<Point> P;

inline void init();
inline vector<Point> Andrew(vector<Point>);
inline double cross(Point, Point, Point);
inline double Area(vector<Point>);
inline double calc(Point, Point, Point);

signed main()
{
IO;
cin >> N;
while (N--) {
cin >> n;
init();
for (int i = 0; i < n; i++) {
cin >> x >> y >> w >> h >> ang;
rad = -PI * ang / 180.0;
Point o(x, y);
P.emplace_back(o + Point(w / 2, h / 2).Rotate(rad));
P.emplace_back(o + Point(w / 2, -h / 2).Rotate(rad));
P.emplace_back(o + Point(-w / 2, h / 2).Rotate(rad));
P.emplace_back(o + Point(-w / 2, -h / 2).Rotate(rad));
area += w * h;
}
sort(P.begin(), P.end());
P = Andrew(P);
cout << fixed << setprecision(1) << area / Area(P) * 100 << " %" << endl;
}
return 0;
}

inline void init()
{
P.clear();
area = 0.0;
}

inline vector<Point> Andrew(vector<Point> p)
{
vector<Point> ch(p.size() * 2);
int m = 0;
for (int i = 0; i < (int)p.size(); i++) {
while (m >= 2 && cross(ch[m - 2], ch[m - 1], p[i]) <= 0)
m--;
ch[m++] = p[i];
}
for (int i = p.size() - 2, t = m + 1; i >= 0; i--) {
while (m >= t && cross(ch[m - 2], ch[m - 1], p[i]) <= 0)
m--;
ch[m++] = p[i];
}
ch.resize(m - 1);
return ch;
}

inline double cross(Point o, Point a, Point b)
{
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

inline double Area(vector<Point> p)
{
double a = 0.0;
for (int i = 2; i < (int)p.size(); i++)
a += calc(p[0], p[i - 1], p[i]);
return a / 2.0;
}

inline double calc(Point a,Point b,Point c)
{
return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}