動態幾何 史蒂芙的泡泡 (解法 2)

題目描述

在處理完數以百計的政事後,受盡折磨的史蒂芙,打算回家好好地休息。 拖著疲倦的身軀,再也無法再容納任何一點複雜計算。從王宮走回寢居的路上, 發現身邊所見的事物都不再圓滑,看起來就像是粗糙的幾何多邊形構成的一切。

打算享受著泡泡浴的史蒂芙,看著眼前的多邊形泡泡,失去原本應有的色澤,那透涼的心境更蒙上了一層灰影

「為什麼是我呢?」感嘆道

伸出手戳著眼前的泡泡,卻飄了過去

「區區的泡泡也跟我作對,嗚嗚」

將一個泡泡視為一個簡單多邊形 $A$,方便起見用一個序列 $a_0, a_1, ..., a_{n-1}$ 表示多邊形 $A$ 的每一個頂點,則會有 $n$ 個線段 $\overline{a_0 a_1}, \overline{a_1 a_2}, \cdots, \overline{a_{n-1} a_0}$

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
5 14
0 0
10 0
10 10
0 10
5 5
1 0 0
1 1 0
1 2 1
1 3 2
3 5.5 5
3 10 -1
3 10 5
1 4 1
3 5.5 5
3 10 -1
3 10 5
2 3
3 5 7.5
3 5 2.5

Sample Output

1
2
3
4
5
6
7
8
1
0
0
0
0
0
0
1

Solution

參閱 動態幾何 史蒂芙的泡泡 (解法 1)

相較於先前的解法 $\mathcal{O}(\log n) - \mathcal{O}(\ast \sqrt{n})$,相當不穩定的嵌套 KD-BRH 的解法,實際上如果單純針對這一題,可以拋開 region search 的操作,只有完全的詢問點是否在多邊形內部,則可以做到 $\mathcal{O}(\log^2 n)$

如同一般的射線法,對詢問點拉出無限延長的線,找到與多邊形的邊相交個數。如果單純把每一條邊拿出來看,最暴力的複雜度為 $\mathcal{O}(n)$,現在要減少查閱的邊數,且透過 rank tree 在 $\mathcal{O}(\log n)$ 累計相交數量。

由於給定的座標不需要動態,則著手離散化 $X = x_0, x_1, \cdots, x_n$,線段樹中的每一個點 $u$ 維護一個 rank tree,把包含者個區段 $[x_l, x_r]$ 的線段通通放入,且保證放入的線段彼此之間不相交 (除了兩端點)。如此一來,當詢問一個點,需要探訪 $\mathcal{O}(\log n)$ 個節點,每個節點 $u$ 需要 $\mathcal{O}(\log n)$ 時間來計算相交數量,最後詢問的複雜度為 $\mathcal{O}(\log^2 n)$。同理,修改點的操作也會在 $\mathcal{O}(\log^2 n)$

實作時,特別注意到與射線方向相同的線段不予處理,按照下面的寫法則是不處理垂直的線段,一來是射線法也不會去計算,二來是線段樹劃分的時候會造成一些邊界問題,由於我們對於點離散,父節點 $[x_l, x_r]$,左右子樹控制的分別為 $[x_l, x_\text{mid}]$$[x_\text{mid}, x_r]$,劃分時會共用中間點。

即使有了上述的概念來解題,我們仍需要維護 rope data structrue 來維護節點的相鄰關係,可以自己實作任何的 binary tree 來達到 $\mathcal{O}(\log n)$,這裡採用 splay tree 示範。


接下來介紹內建黑魔法 PBDS (policy-based data structure) 和 rope。很多人都提及到這些非正式的 STL 函式庫,只有在 gcc/g++ 裡面才有附錄,如果是 clang 等其他編譯器可能是沒有辦法的。所以上傳相關代碼要看 OJ 是否採用純正的 gcc/g++。

參考資料:

PBDS 比較常用在 rank tree 和 heap,由於代碼量非常多,用內建防止 code length exceed limitation 的出現,也不妨是個好辦法。用 rank tree 的每一個詢問操作皆在 $\mathcal{O}(\log n)$,而 heap 選擇 thin heap 或 pairing heap,除了 pop 操作外,皆為 $\mathcal{O}(1)$,在對最短路徑問題上別有優勢。

而這一題不太適用 SGI rope,原因在於雖為 $\mathcal{O}(\log n)$ 操作,但它原本就為了仿作 string 而強迫變成可持久化的引數結構,導致每一個操作需要額外的開銷來減少內存使用。由於此題經常在單一元素上操作,SGI rope 對於單一元素效能不彰,以造成嚴重的逾時。

這裡仍提及和示範這些概念的資料結構,哪天正式編入標準函式庫,想必效能問題都已解決。


  • KD BRH AC(0.2s, 10 MB)
  • PBDS + SPLAY AC(0.3s, 38 MB)
  • PBDS + SGI rope AC(0.5s, 41 MB)
    本機 MINGW gcc 4.9 c++ 11 編譯完運行最大的測資需要 20 倍慢於其他寫法,但是上傳到 ZJ 的 gcc 7 又追回去了。於是下載 CYGWIN gcc 7 測試結果與 ZJ 運行結果相當,對於需要調適的人,建議在新版上測試。

用 splay tree 模擬 rope 的時候,會遇到循序非遞減的走訪,這時候若不斷地旋轉至根,會在之後的操作造成退化,常數稍微大一點,雖然在迭代過程中造就好的快取效能,很快地在 $\mathcal{O}(1)$ 訪問到相鄰的節點,卻在下一次的插入/刪除操作中變慢。一些變異的版本中,如只在插入/刪除操作中旋轉至根,在查找操作中不旋轉,或者限制旋轉的深度。雖然有一些特別的退化操作,splay 仍舊是某些 OS 場景中使用的資料結構,現實總是很特別的。

In 2000, Danny Sleator and Robert Tarjan won the ACM Kanellakis Theory and Practice Award for their papers on splay trees and amortized analysis. Splay trees are used in Windows NT (in the virtual memory, networking, and file system code), the gcc compiler and GNU C++ library, the sed string editor, Fore Systems network routers, the most popular implementation of Unix malloc, Linux loadable kernel modules, and in much other software.

PBDS + SPLAY

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
struct Mesh {
static const int MAXN = 1e5 + 5;
int pt[MAXN][2];
vector<int> X;
void read(int n) {
for (int i = 0; i < n; i++)
scanf("%d %d", &pt[i][0], &pt[i][1]);
X.clear(); X.reserve(n);
for (int i = 0; i < n; i++)
X.push_back(pt[i][0]);
sort(X.begin(), X.end());
X.erase(unique(X.begin(), X.end()), X.end());
}
} mesh;
class SplayTree {
public:
struct Node {
Node *ch[2], *fa;
int size; int data;
Node() {
ch[0] = ch[1] = fa = NULL;
size = 1;
}
bool is_root() {
return fa->ch[0] != this && fa->ch[1] != this;
}
};
Node *root, *EMPTY;
void pushdown(Node *u) {}
void pushup(Node *u) {
if (u->ch[0] != EMPTY) pushdown(u->ch[0]);
if (u->ch[1] != EMPTY) pushdown(u->ch[1]);
u->size = 1 + u->ch[0]->size + u->ch[1]->size;
}
void setch(Node *p, Node *u, int i) {
if (p != EMPTY) p->ch[i] = u;
if (u != EMPTY) u->fa = p;
}
SplayTree() {
EMPTY = new Node();
EMPTY->fa = EMPTY->ch[0] = EMPTY->ch[1] = EMPTY;
EMPTY->size = 0;
}
void init() {
root = EMPTY;
}
Node* newNode() {
Node *u = new Node();
u->fa = u->ch[0] = u->ch[1] = EMPTY;
return u;
}
void rotate(Node *x) {
Node *y;
int d;
y = x->fa, d = y->ch[1] == x ? 1 : 0;
x->ch[d^1]->fa = y, y->ch[d] = x->ch[d^1];
x->ch[d^1] = y;
if (!y->is_root())
y->fa->ch[y->fa->ch[1] == y] = x;
x->fa = y->fa, y->fa = x;
pushup(y);
}
void deal(Node *x) {
if (!x->is_root()) deal(x->fa);
pushdown(x);
}
void splay(Node *x, Node *below) {
if (x == EMPTY) return ;
Node *y, *z;
deal(x);
while (!x->is_root() && x->fa != below) {
y = x->fa, z = y->fa;
if (!y->is_root() && y->fa != below) {
if (y->ch[0] == x ^ z->ch[0] == y)
rotate(x);
else
rotate(y);
}
rotate(x);
}
pushup(x);
if (x->fa == EMPTY) root = x;
}
Node* prevNode(Node *u) {
splay(u, EMPTY);
return maxNode(u->ch[0]);
}
Node* nextNode(Node *u) {
splay(u, EMPTY);
return minNode(u->ch[1]);
}
Node* minNode(Node *u) {
Node *p = u->fa;
for (; pushdown(u), u->ch[0] != EMPTY; u = u->ch[0]);
splay(u, p);
return u;
}
Node* maxNode(Node *u) {
Node *p = u->fa;
for (; pushdown(u), u->ch[1] != EMPTY; u = u->ch[1]);
splay(u, p);
return u;
}
Node* findPos(int pos) { // [0...]
for (Node *u = root; u != EMPTY;) {
pushdown(u);
int t = u->ch[0]->size;
if (t == pos) {
splay(u, EMPTY);
return u;
}
if (t > pos)
u = u->ch[0];
else
u = u->ch[1], pos -= t + 1;
}
return EMPTY;
}
tuple<int, int, int> insert(int data, int pos) { // make [pos] = data
Node *p, *q = findPos(pos);
Node *x = newNode(); x->data = data;
if (q == EMPTY) {
p = maxNode(root), splay(p, EMPTY);
setch(x, p, 0);
splay(x, EMPTY);
} else {
splay(q, EMPTY), p = q->ch[0];
setch(x, p, 0), setch(x, q, 1);
setch(q, EMPTY, 0);
splay(q, EMPTY);
p = prevNode(x);
}
if (p == EMPTY) p = maxNode(root);
if (q == EMPTY) q = minNode(root);
return make_tuple(p->data, data, q->data);
}
tuple<int, int, int> remove(int pos) {
Node *x = findPos(pos), *p, *q;
p = prevNode(x), q = nextNode(x);
if (p != EMPTY && q != EMPTY) {
setch(p, q, 1);
p->fa = EMPTY, splay(q, EMPTY);
} else if (p != EMPTY) {
p->fa = EMPTY, root = p;
} else {
q->fa = EMPTY, root = q;
}
int del = x->data;
delete x;
if (p == EMPTY) p = maxNode(root);
if (q == EMPTY) q = minNode(root);
return make_tuple(p->data, del, q->data);
}
int size() {
return root == EMPTY ? 0 : root->size;
}
} mlist;
struct Pt {
double x, y;
Pt() {}
Pt(int xy[]):Pt(xy[0], xy[1]) {}
Pt(double x, double y):x(x), y(y) {}
bool operator<(const Pt &o) const {
if (x != o.x) return x < o.x;
return y < o.y;
}
};
struct PtP {
static double x;
Pt p, q;
PtP(Pt a, Pt b) {
p = a, q = b;
if (q < p)
swap(p, q);
}
double interpolate(const Pt& p1, const Pt& p2, double& x) const {
if (p1.x == p2.x) return min(p1.y, p2.y);
return p1.y + (p2.y - p1.y) / (p2.x - p1.x) * (x - p1.x);
}
bool operator<(const PtP &o) const {
return interpolate(p, q, x) < interpolate(o.p, o.q, x);
}
};
double PtP::x = 1;
struct SegSeg {
struct Node {
Node *lson, *rson;
tree<pair<PtP, int>, null_type, less<pair<PtP, int>>, rb_tree_tag, tree_order_statistics_node_update> segs;
Node() {
lson = rson = NULL;
}
};
Node *root;
int xn;
Node* newNode() {
return new Node();
}
void freeNode(Node *u) {
free(u);
}
void init() {
root = NULL;
xn = mesh.X.size();
}
void insert(tuple<int, int, int> e) {
int p, q, r; tie(p, q, r) = e;
remove(0, xn-1, {PtP(Pt(mesh.pt[p]), Pt(mesh.pt[r])), r});
insert(0, xn-1, {PtP(Pt(mesh.pt[p]), Pt(mesh.pt[q])), q});
insert(0, xn-1, {PtP(Pt(mesh.pt[q]), Pt(mesh.pt[r])), r});
}
void remove(tuple<int, int, int> e) {
int p, q, r; tie(p, q, r) = e;
remove(0, xn-1, {PtP(Pt(mesh.pt[p]), Pt(mesh.pt[q])), q});
remove(0, xn-1, {PtP(Pt(mesh.pt[q]), Pt(mesh.pt[r])), r});
insert(0, xn-1, {PtP(Pt(mesh.pt[p]), Pt(mesh.pt[r])), r});
}
int inside(double x, double y) {
PtP::x = x;
return count(root, 0, xn-1, x, y)&1;
}
int count(Node* u, int l, int r, double x, double y) {
if (u == NULL)
return 0;
int ret = 0;
if ((mesh.X[l] > x) != (mesh.X[r] > x))
ret += u->segs.order_of_key({PtP(Pt(x, y), Pt(x, y)), -1});
int m = (l+r)/2;
if (x <= mesh.X[m])
ret += count(u->lson, l, m, x, y);
if (x >= mesh.X[m])
ret += count(u->rson, m, r, x, y);
return ret;
}
void insert(int l, int r, pair<PtP, int> s) {
if (s.first.p.x != s.first.q.x)
insert(root, l, r, s);
}
void remove(int l, int r, pair<PtP, int> s) {
if (s.first.p.x != s.first.q.x)
remove(root, l, r, s);
}
void insert(Node* &u, int l, int r, pair<PtP, int> s) {
if (u == NULL)
u = newNode();
if (s.first.p.x <= mesh.X[l] && mesh.X[r] <= s.first.q.x) {
PtP::x = (mesh.X[l] + mesh.X[r])/2.0;
u->segs.insert(s);
return;
}
int m = (l+r)/2;
if (s.first.q.x <= mesh.X[m]) insert(u->lson, l, m, s);
else if (s.first.p.x >= mesh.X[m]) insert(u->rson, m, r, s);
else insert(u->lson, l, m, s), insert(u->rson, m, r, s);
}
void remove(Node* u, int l, int r, pair<PtP, int> s) {
if (u == NULL)
return;
if (s.first.p.x <= mesh.X[l] && mesh.X[r] <= s.first.q.x) {
PtP::x = (mesh.X[l] + mesh.X[r])/2.0;
u->segs.erase(s);
return;
}
int m = (l+r)/2;
if (s.first.q.x <= mesh.X[m]) remove(u->lson, l, m, s);
else if (s.first.p.x >= mesh.X[m]) remove(u->rson, m, r, s);
else remove(u->lson, l, m, s), remove(u->rson, m, r, s);
}
} mbrh;
int main() {
int n, m, cmd, x, pos;
double px, py;
scanf("%d %d", &n, &m);
mesh.read(n);
mlist.init(), mbrh.init();
for (int i = 0; i < m; i++) {
scanf("%d", &cmd);
if (cmd == 1) {
scanf("%d %d", &x, &pos);
mbrh.insert(mlist.insert(x, pos));
} else if (cmd == 2) {
scanf("%d", &x);
mbrh.remove(mlist.remove(x));
} else {
scanf("%lf %lf", &px, &py);
puts(mbrh.inside(px, py) ? "1" : "0");
}
}
return 0;
}

PBDS + ROPE

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
#include <bits/stdc++.h>
using namespace std;
#include <ext/rope>
using namespace __gnu_cxx;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
struct Mesh {
static const int MAXN = 1e5 + 5;
int pt[MAXN][2];
vector<int> X;
void read(int n) {
for (int i = 0; i < n; i++)
scanf("%d %d", &pt[i][0], &pt[i][1]);
X.clear(); X.reserve(n);
for (int i = 0; i < n; i++)
X.push_back(pt[i][0]);
sort(X.begin(), X.end());
X.erase(unique(X.begin(), X.end()), X.end());
}
} mesh;
class Rope {
public:
rope<int> r;
void init() {
r.clear();
}
int next(rope<int>::const_iterator it) {
it++;
if (it == r.end())
return *r.begin();
return *it;
}
int prev(rope<int>::const_iterator it) {
if (it == r.begin())
return *r.rbegin();
it--;
return *it;
}
tuple<int, int, int> insert(int data, int pos) {
r.insert(pos, data);
auto it = r.begin() + pos;
int p = prev(it);
int q = next(it);
return make_tuple(p, data, q);
}
tuple<int, int, int> remove(int pos) {
auto it = r.begin() + pos;
int del = *it;
int p = prev(it);
int q = next(it);
r.erase(pos, 1);
return make_tuple(p, del, q);
}
} mlist;
struct Pt {
double x, y;
Pt() {}
Pt(int xy[]):Pt(xy[0], xy[1]) {}
Pt(double x, double y):x(x), y(y) {}
bool operator<(const Pt &o) const {
if (x != o.x) return x < o.x;
return y < o.y;
}
};
struct PtP {
static double x;
Pt p, q;
PtP(Pt a, Pt b) {
p = a, q = b;
if (q < p)
swap(p, q);
}
double interpolate(const Pt& p1, const Pt& p2, double& x) const {
if (p1.x == p2.x) return min(p1.y, p2.y);
return p1.y + (p2.y - p1.y) / (p2.x - p1.x) * (x - p1.x);
}
bool operator<(const PtP &o) const {
return interpolate(p, q, x) < interpolate(o.p, o.q, x);
}
};
double PtP::x = 1;
struct SegSeg {
struct Node {
Node *lson, *rson;
tree<pair<PtP, int>, null_type, less<pair<PtP, int>>, rb_tree_tag, tree_order_statistics_node_update> segs;
Node() {
lson = rson = NULL;
}
};
Node *root;
int xn;
Node* newNode() {
return new Node();
}
void init() {
root = NULL;
xn = mesh.X.size();
}
void insert(tuple<int, int, int> e) {
int p, q, r; tie(p, q, r) = e;
remove(0, xn-1, {PtP(Pt(mesh.pt[p]), Pt(mesh.pt[r])), r});
insert(0, xn-1, {PtP(Pt(mesh.pt[p]), Pt(mesh.pt[q])), q});
insert(0, xn-1, {PtP(Pt(mesh.pt[q]), Pt(mesh.pt[r])), r});
}
void remove(tuple<int, int, int> e) {
int p, q, r; tie(p, q, r) = e;
remove(0, xn-1, {PtP(Pt(mesh.pt[p]), Pt(mesh.pt[q])), q});
remove(0, xn-1, {PtP(Pt(mesh.pt[q]), Pt(mesh.pt[r])), r});
insert(0, xn-1, {PtP(Pt(mesh.pt[p]), Pt(mesh.pt[r])), r});
}
int inside(double x, double y) {
PtP::x = x;
return count(root, 0, xn-1, x, y)&1;
}
int count(Node* u, int l, int r, double x, double y) {
if (u == NULL)
return 0;
int ret = 0;
if ((mesh.X[l] > x) != (mesh.X[r] > x))
ret += u->segs.order_of_key({PtP(Pt(x, y), Pt(x, y)), -1});
if (l == r)
return ret;
int m = (l+r)/2;
if (x <= mesh.X[m])
ret += count(u->lson, l, m, x, y);
if (x >= mesh.X[m])
ret += count(u->rson, m, r, x, y);
return ret;
}
void insert(int l, int r, pair<PtP, int> s) {
if (s.first.p.x != s.first.q.x)
insert(root, l, r, s);
}
void remove(int l, int r, pair<PtP, int> s) {
if (s.first.p.x != s.first.q.x)
remove(root, l, r, s);
}
void insert(Node* &u, int l, int r, pair<PtP, int> s) {
if (u == NULL)
u = newNode();
if (s.first.p.x <= mesh.X[l] && mesh.X[r] <= s.first.q.x) {
PtP::x = (mesh.X[l] + mesh.X[r])/2.0;
u->segs.insert(s);
return;
}
if (l == r)
return;
int m = (l+r)/2;
if (s.first.q.x <= mesh.X[m]) insert(u->lson, l, m, s);
else if (s.first.p.x >= mesh.X[m]) insert(u->rson, m, r, s);
else insert(u->lson, l, m, s), insert(u->rson, m, r, s);
}
void remove(Node* &u, int l, int r, pair<PtP, int> s) {
if (u == NULL)
return;
if (s.first.p.x <= mesh.X[l] && mesh.X[r] <= s.first.q.x) {
PtP::x = (mesh.X[l] + mesh.X[r])/2.0;
u->segs.erase(s);
return;
}
if (l == r)
return;
int m = (l+r)/2;
if (s.first.q.x <= mesh.X[m]) remove(u->lson, l, m, s);
else if (s.first.p.x >= mesh.X[m]) remove(u->rson, m, r, s);
else remove(u->lson, l, m, s), remove(u->rson, m, r, s);
}
} mbrh;
int main() {
int n, m, cmd, x, pos;
double px, py;
scanf("%d %d", &n, &m);
mesh.read(n);
mlist.init(), mbrh.init();
for (int i = 0; i < m; i++) {
scanf("%d", &cmd);
if (cmd == 1) {
scanf("%d %d", &x, &pos);
mbrh.insert(mlist.insert(x, pos));
} else if (cmd == 2) {
scanf("%d", &x);
mbrh.remove(mlist.remove(x));
} else {
scanf("%lf %lf", &px, &py);
puts(mbrh.inside(px, py) ? "1" : "0");
}
}
return 0;
}
Read More +

敲落的聲響

那一刻

2019 年的開始,研發替代役過去一年三個月,迎來人生巔峰的二十五歲。曾經努力積賺的學習,在這個當下不斷地被提取,已經無法再次追逐那夢想中的人生,那等跨不過的門檻,對於不斷地分析計算的我,早已算不出任何的可能性。

「全新投入工作中,過著非常平凡順遂的生活。監視著表面的自己是否有不斷地往前進,責怪著那個自己,為什麼沒有好好面對眼前的重要事物。」-《秒速 5 厘米》

倘若停止督促自己這般前進的動力,又如何面對過去,原本希望在未來有所成就的自己。也許要有所改變,正也因為過去的累積才造就現在的我,如果可以這麼輕易地改變,那思考方式就像徹底換了個人似的,四分五裂。

「過去,一直抱持著專一的新。對於無法維持這種想法的自己,一直以來都無法釋懷。」-《秒速 5 厘米》

即使有了工作,認識了新的同事,那無非也只是個工作,社交禮儀下的對談。彼此之間都過著各自的生活,每當論及自己的話題時,總是不知道要從哪裡找出,不受蜚言蜚語的內容。因為總是過著這樣的生活,每天走著兩點一線的路線,不曾偏離的軌跡要怎麼聊著好幾個日子。

要在外頭活出有趣的日子,那是如此困難的題目,每踏一步就是數以百萬的分枝,一個人也許走到哪算到哪,但總是無法歸納一個「樂」的結語。編出讓其他人能夠理解的話語,不斷地瞞騙自己,事實上並沒有這樣子的感受吧。我們之間並沒有好聊的,沒有交集的交流,就不要增添麻煩給彼此了。

「總覺得…已經很久沒有跟人說過話了。」-《秒速 5 厘米》

講講你喜歡的事情吧。無法輕易地說出喜歡,但從你們看來,擺明就是喜歡某些事情,才至於身邊都是這種事物的存在。這種老是亂下評論的人。若從口中道出「喜歡」兩個字,是否又可以增加對方強而有力的定論。身邊只有那些選項時,也只能從那些裡選,不斷地選了下去,那還能稱作「喜歡」的事物,而不是受到「束縛」的體現嗎?

「"喜歡" 是一個束縛的詞」-《終將成為你》

前一刻

投入工作的那一年裡,不斷地翻盤革新,交付著重大包袱,那些面臨到不得不再次攤開的問題,早已沒有人可以述說那段歷史,而現在束手無撤的工程師們,無疑地想邁向全新的架構,到底要怎麼寫才可以銜接原本的需求,有多少人願意花時間去理解,而又有多少人願意花時間等你,不斷地估算那種看不到結局的日子有多遠,又細數著下一個里程有多近。那種龐大的壓迫,能不斷地走出下一步的策略在哪?

「我該成為怎樣的人,來度過餘生」-《終將成為你》

把畢生所學的技術填充進去,那樣就可以解決了嗎?發現有所缺陷的解法,想著問題以不同方式分解,再以不同方式擊破。想不出來就去休息吧。解解別的題目,再回來思考,重置於不同狀態的思維出發,就有機會看到問題的另一面。

然而,過著不斷轉換的日子,發現也來到了三千五百題,這令人羞於心的數字,表示了閒與宅的程度。而真正聰明的人,理應用最少的工具解決最多的問題,也就是以最少的題數,達成最好的成就。試圖從那些題目中淬煉新想法,果然還太愚笨了些,僅僅只是知道的比人多,卻沒有好好地比任何人都深入了解。

「但是我沒辦法在其他人面前,不做特別的自己」-《終將成為你》

下一刻

一年的過去,收到一些學長們的問候,馬上就猜到是來拉人換工作的。現在的我,有那種能力獲得青睞嗎?而現在的位子,是否只是被人感受到這傢伙堪用?算了一算,那些提及的工作內容與薪水,到底以什麼樣的比例才算活得心安,能否不為了下一個日子前進而煩惱。原本應屬於我的日子,是哪一種?

「雖然很遺憾,才能這種東西是有個體差別的,若用鳥類來舉例,我的羽翼是靠腳踏驅動的那種」-《3月的獅子》

「如果,不像惡鬼般地逼迫自己,滿身大汗地蹬下去,一瞬間就會墜落地面」-《3月的獅子》

「如果停止蹬踏的話,若是將能量用再其他的事情上面,就算只是百分之幾,雖不至於墜下去,高度也會降低」-《3月的獅子》

親人、同學、同事,每一個像是完成里程碑地一一度過了關卡,看到自己的下一關只剩下工作,也不知道工作的下一步是為了生活,而生活要去煩惱工作。如果只是這樣子不斷地循環,定義的輪廓已有了雛形,明瞭一切的那時也到了盡頭。如此地羨慕有目標走到下一步,而我只是在等待事情的落幕。

現在的處境到底是雞生蛋,還是蛋生雞?

「我們要一直活下去哦」-《盾之勇者成名錄》

「我接受了現實,回歸平靜」-《我想吃掉你的胰臟》

Read More +

動態幾何 史蒂芙的泡泡 (解法 1)

題目描述請至 Zerojudge e021: 史蒂芙的泡泡 查閱詳細內容

題目描述

在處理完數以百計的政事後,受盡折磨的史蒂芙,打算回家好好地休息。 拖著疲倦的身軀,再也無法再容納任何一點複雜計算。從王宮走回寢居的路上, 發現身邊所見的事物都不再圓滑,看起來就像是粗糙的幾何多邊形構成的一切。

打算享受著泡泡浴的史蒂芙,看著眼前的多邊形泡泡,失去原本應有的色澤,那透涼的心境更蒙上了一層灰影

「為什麼是我呢?」感嘆道

伸出手戳著眼前的泡泡,卻飄了過去

「區區的泡泡也跟我作對,嗚嗚」

將一個泡泡視為一個簡單多邊形 $A$,方便起見用一個序列 $a_0, a_1, ..., a_{n-1}$ 表示多邊形 $A$ 的每一個頂點,則會有 $n$ 個線段 $\overline{a_0 a_1}, \overline{a_1 a_2}, \cdots, \overline{a_{n-1} a_0}$

解法

從能找到的論文「A Unified Approach to Dynamic Point Location, Ray Shooting, and Shortest Paths in Planar Maps」 得知操作更新 $\mathcal{O}(\log^3 n)$,詢問操作 $\mathcal{O}(\log n)$,這一個實作難度估計沒辦法在 10K 限制下完成 (代碼上傳長度上限)。

從動態梯形剖分開始,複雜度就相當高了,而論文後要有類似輕重鏈剖分的概念,將對偶圖產生的節點以輕重邊保存,接著再維護雙線輪廓,讓相連的連續重邊可以保存左右兩側的輪廓,… 資訊量龐大,想到一些可能未提及的邊界案例,實作相當困難。而從其他題目的經驗中,當設計到 $\mathcal{O}(\log^2 n)$ 的操作時,由於操作常數大,運行時間可能無法匹敵 $\mathcal{O}(\sqrt{n})$ 的算法。

那麼有沒有其他的替代方案,只需要跑得比暴力法還要快就行?特別小心,暴力法找一個點是否在多邊形內,需要 $\mathcal{O}(n)$ 的時間,且快取效果非常好,很容易做到 SIMD 的平行技術。

首先,解決維護多邊形點集序列,可以使用任何的平衡樹完成,若採用 splay tree 在均攤 $\text{Amortized} \; \mathcal{O}(\log n)$。使用 treap 也可以完成這類操作,還可以做到額外的持久化功能。接著,修改點的操作,可以轉換成替換一個點的下一個點,因此將點放在 KD tree 上,而維護下一個點相當於把每一個節點擴充成 BRH。

接著,當解決點是否在多邊形內時,可走訪 BRH 找射線穿過的交點個數,此時複雜度至少為 $\mathcal{O}(\sqrt{n} + k)$,其中 $k$ 為交點個數。我們可以額外維護多邊形的順逆時針來優化搜尋空間,最後一個接觸的線段方向,額外提供奇偶數來判斷該點是否在內側,然後把射線縮短到交點到詢問點之間。不斷地縮短搜尋空間下,大部分的情況為 $\mathcal{O}(\sqrt{n})$,拋開了原本存在的 $k$

由於是封閉的簡單多邊形,所以當邊的疏密程度不一時,KD tree 轉換 BRH 會造成額外的負擔,bounding box 無法有效提供分割空間的功能。那麼在實際搜尋情況,額外走訪的節點與平面分布有關,這部分就不好分析。如果有更好的想法,歡迎分享。

現在實作動態 KD tree 必須有替罪羊樹 Scapegoat tree 的概念,再掛上 BRH 的想法,提供了相對有效率的動態方法來查詢點是否在多邊形內部。若把維護點序列的 splay tree 換成 treap,便可以做到持久化的動態幾何操作,這便是一開始想要的目標。

如果梯形剖分也可以持久化?暫時還不想去思考,那思考的容器要多大呢?

參考解法

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
#include <bits/stdc++.h>
using namespace std;
struct Mesh {
static const int MAXN = 1e5 + 5;
int pt[MAXN][2];
void read(int n) {
for (int i = 0; i < n; i++)
scanf("%d %d", &pt[i][0], &pt[i][1]);
}
} mesh;
class SplayTree {
public:
struct Node {
Node *ch[2], *fa;
int size; int data;
Node() {
ch[0] = ch[1] = fa = NULL;
size = 1;
}
bool is_root() {
return fa->ch[0] != this && fa->ch[1] != this;
}
};
Node *root, *EMPTY;
void pushdown(Node *u) {}
void pushup(Node *u) {
if (u->ch[0] != EMPTY) pushdown(u->ch[0]);
if (u->ch[1] != EMPTY) pushdown(u->ch[1]);
u->size = 1 + u->ch[0]->size + u->ch[1]->size;
}
void setch(Node *p, Node *u, int i) {
if (p != EMPTY) p->ch[i] = u;
if (u != EMPTY) u->fa = p;
}
SplayTree() {
EMPTY = new Node();
EMPTY->fa = EMPTY->ch[0] = EMPTY->ch[1] = EMPTY;
EMPTY->size = 0;
}
void init() {
root = EMPTY;
}
Node* newNode() {
Node *u = new Node();
u->fa = u->ch[0] = u->ch[1] = EMPTY;
return u;
}
void rotate(Node *x) {
Node *y;
int d;
y = x->fa, d = y->ch[1] == x ? 1 : 0;
x->ch[d^1]->fa = y, y->ch[d] = x->ch[d^1];
x->ch[d^1] = y;
if (!y->is_root())
y->fa->ch[y->fa->ch[1] == y] = x;
x->fa = y->fa, y->fa = x;
pushup(y);
}
void deal(Node *x) {
if (!x->is_root()) deal(x->fa);
pushdown(x);
}
void splay(Node *x, Node *below) {
if (x == EMPTY) return ;
Node *y, *z;
deal(x);
while (!x->is_root() && x->fa != below) {
y = x->fa, z = y->fa;
if (!y->is_root() && y->fa != below) {
if (y->ch[0] == x ^ z->ch[0] == y)
rotate(x);
else
rotate(y);
}
rotate(x);
}
pushup(x);
if (x->fa == EMPTY) root = x;
}
Node* prevNode(Node *u) {
splay(u, EMPTY);
return maxNode(u->ch[0]);
}
Node* nextNode(Node *u) {
splay(u, EMPTY);
return minNode(u->ch[1]);
}
Node* minNode(Node *u) {
Node *p = u->fa;
for (; pushdown(u), u->ch[0] != EMPTY; u = u->ch[0]);
splay(u, p);
return u;
}
Node* maxNode(Node *u) {
Node *p = u->fa;
for (; pushdown(u), u->ch[1] != EMPTY; u = u->ch[1]);
splay(u, p);
return u;
}
Node* findPos(int pos) { // [0...]
for (Node *u = root; u != EMPTY;) {
pushdown(u);
int t = u->ch[0]->size;
if (t == pos) {
splay(u, EMPTY);
return u;
}
if (t > pos)
u = u->ch[0];
else
u = u->ch[1], pos -= t + 1;
}
return EMPTY;
}
tuple<int, int, int> insert(int data, int pos) { // make [pos] = data
Node *p, *q = findPos(pos);
Node *x = newNode(); x->data = data;
if (q == EMPTY) {
p = maxNode(root), splay(p, EMPTY);
setch(x, p, 0);
splay(x, EMPTY);
} else {
splay(q, EMPTY), p = q->ch[0];
setch(x, p, 0), setch(x, q, 1);
setch(q, EMPTY, 0);
splay(q, EMPTY);
p = prevNode(x);
}
if (p == EMPTY) p = maxNode(root);
if (q == EMPTY) q = minNode(root);
return make_tuple(p->data, data, q->data);
}
tuple<int, int, int> remove(int pos) {
Node *x = findPos(pos), *p, *q;
p = prevNode(x), q = nextNode(x);
if (p != EMPTY && q != EMPTY) {
setch(p, q, 1);
p->fa = EMPTY, splay(q, EMPTY);
} else if (p != EMPTY) {
p->fa = EMPTY, root = p;
} else {
q->fa = EMPTY, root = q;
}
int del = x->data;
free(x);
if (p == EMPTY) p = maxNode(root);
if (q == EMPTY) q = minNode(root);
return make_tuple(p->data, del, q->data);
}
int size() {
return root == EMPTY ? 0 : root->size;
}
} mlist;
static inline int log2int(int x) {
return 31 - __builtin_clz(x);
}
static inline int64_t h(int p, int q) {
return (int64_t) mesh.pt[p][0]*mesh.pt[q][1] - (int64_t) mesh.pt[p][1]*mesh.pt[q][0];
}
struct KDBRH {
static constexpr double ALPHA = 0.75;
static constexpr double LOG_ALPHA = log2(1.0 / ALPHA);
struct Pt {
int d[2];
Pt() {}
Pt(int xy[]):Pt(xy[0], xy[1]) {}
Pt(int x, int y) {d[0] = x, d[1] = y;}
bool operator==(const Pt &x) const {
return d[0] == x.d[0] && d[1] == x.d[1];
}
static Pt NaN() {return Pt(INT_MIN, INT_MIN);}
int isNaN() {return d[0] == INT_MIN;}
};
struct PtP {
Pt p, q;
PtP(Pt p, Pt q): p(p), q(q) {}
};
struct cmpAxis {
int k;
cmpAxis(int k): k(k) {}
bool operator() (const PtP &x, const PtP &y) const {
return x.p.d[k] < y.p.d[k];
}
};
struct BBox {
#define KDMIN(a, b, c) {a[0] = min(b[0], c[0]), a[1] = min(b[1], c[1]);}
#define KDMAX(a, b, c) {a[0] = max(b[0], c[0]), a[1] = max(b[1], c[1]);}
int l[2], r[2];
BBox() {}
BBox(int a[], int b[]) {
KDMIN(l, a, b); KDMAX(r, a, b);
}
void expand(Pt p) {
KDMIN(l, l, p.d); KDMAX(r, r, p.d);
}
void expand(BBox b) {
KDMIN(l, l, b.l); KDMAX(r, r, b.r);
}
inline int raycast(double x, double fx, double y) {
return l[1] <= y && y <= r[1] && r[0] >= x && l[0] <= fx;
}
static BBox init() {
BBox b; b.l[0] = b.l[1] = INT_MAX, b.r[0] = b.r[1] = INT_MIN;
return b;
}
};
struct Node {
Node *lson, *rson;
Pt pt, qt;
BBox box;
int size; int8_t used;
Node() {}
void init() {
lson = rson = NULL;
size = 1, used = 1;
pt = qt = Pt::NaN();
}
bool hasBox() { return box.l[0] <= box.r[0]; }
void pushup() {
size = used;
if (lson) size += lson->size;
if (rson) size += rson->size;
pushupBox();
}
void pushupBox() {
BBox t = BBox::init();
if (!qt.isNaN())
t.expand(pt), t.expand(qt);
if (lson && lson->hasBox())
t.expand(lson->box);
if (rson && rson->hasBox())
t.expand(rson->box);
box = t;
}
double interpolate(double y) {
if (pt.d[1] == qt.d[1]) return pt.d[0];
return pt.d[0] + (qt.d[0] - pt.d[0]) * (y - pt.d[1]) / (qt.d[1] - pt.d[1]);
}
};
Node *root;
vector<PtP> A;
int64_t area;
Node _mem[262144];
int gc[262144], gci, memi;
Node* newNode() {
Node *u = gci >= 0 ? &_mem[gc[gci--]] : &_mem[memi++];
u->init();
return u;
}
void freeNode(Node *u) {
gc[++gci] = u-_mem;
}
void init() {
root = NULL, area = 0;
gci = -1, memi = 0;
}
void insert(tuple<int, int, int> e) {
int p, q, r; tie(p, q, r) = e;
insert(root, 0, Pt(mesh.pt[q]), Pt(mesh.pt[p]), log2int(size()) / LOG_ALPHA);
changeNode(root, 0, Pt(mesh.pt[r]), Pt(mesh.pt[q]));
area += h(p, q) + h(q, r) - h(p, r);
}
void remove(tuple<int, int, int> e) {
int p, q, r; tie(p, q, r) = e;
remove(root, 0, Pt(mesh.pt[q]), log2int(size()) / LOG_ALPHA);
changeNode(root, 0, Pt(mesh.pt[r]), Pt(mesh.pt[p]));
area -= h(p, q) + h(q, r) - h(p, r);
}
int RAY_T;
double RAY_X;
vector<double> X;
int inside(double x, double y) {
if (area == 0) return 0;
X.clear(), RAY_X = 1e+12, RAY_T = -1;
raycast(root, x, y);
if (RAY_T < 0)
return X.size()&1;
int pass = (area > 0) == RAY_T;
for (auto &x : X)
pass += x <= RAY_X;
return pass&1;
}
int size() { return root == NULL ? 0 : root->size; }
inline int isbad(Node *u, Node *v) {
if (u == root) return 1;
int l = v ? v->size : 0;
l = max(l, u->size-u->used-l);
return l > u->size * ALPHA;
}
Node* build(int k, int l, int r) {
if (l > r) return NULL;
int mid = (l + r)>>1;
Node *ret = newNode();
sort(A.begin()+l, A.begin()+r+1, cmpAxis(k));
while (mid > l && A[mid].p.d[k] == A[mid-1].p.d[k])
mid--;
tie(ret->pt, ret->qt) = tie(A[mid].p, A[mid].q);
ret->lson = build(!k, l, mid-1);
ret->rson = build(!k, mid+1, r);
ret->pushup();
return ret;
}
void flatten(Node *u) {
if (!u) return ;
flatten(u->lson);
flatten(u->rson);
if (u->used) A.emplace_back(u->pt, u->qt);
freeNode(u);
}
void changeNode(Node *u, int k, Pt x, Pt qt) {
if (!u) return;
if (x == u->pt) {
u->qt = qt, u->pushupBox();
return;
}
changeNode(x.d[k] < u->pt.d[k] ? u->lson : u->rson, !k, x, qt);
u->pushupBox();
}
void rebuild(Node* &u, int k) {
A.clear(), A.reserve(u->size);
flatten(u);
u = build(k, 0, A.size()-1);
}
bool insert(Node* &u, int k, Pt x, Pt y, int d) {
if (!u) {
u = newNode(), u->pt = x, u->qt = y, u->pushup();
return d <= 0;
}
if (x == u->pt) {
u->used = 1, u->qt = y, u->pushup();
return d <= 0;
}
auto &v = x.d[k] < u->pt.d[k] ? u->lson : u->rson;
int t = insert(v, !k, x, y, d-1);
u->pushup();
if (t && !isbad(u, v))
return 1;
if (t) rebuild(u, k);
return 0;
}
bool remove(Node* &u, int k, Pt x, int d) {
if (!u)
return d <= 0;
if (x == u->pt) {
if (u->lson || u->rson)
u->used = 0, u->qt = Pt::NaN(), u->pushup();
else
freeNode(u), u = NULL;
return d <= 0;
}
auto &v = x.d[k] < u->pt.d[k] ? u->lson : u->rson;
int t = remove(v, !k, x, d-1);
u->pushup();
if (t && !isbad(u, v))
return 1;
if (t) rebuild(u, k);
return 0;
}
inline int cast(Node *u, double x, double y) {
if (u->qt.isNaN() || (u->pt.d[1] > y) == (u->qt.d[1] > y))
return 0;
double tx = u->interpolate(y);
if (tx <= x || tx > RAY_X)
return 0;
RAY_X = tx, RAY_T = u->pt.d[1] < u->qt.d[1];
X.emplace_back(tx);
return 1;
}
Node* stk[128];
void raycast(Node *u, double x, double y) {
#define pushstk(u) {*p++ = u;}
Node **p = stk;
pushstk(u);
while (p > stk) {
u = *--p;
if (!u || !u->size || !u->box.raycast(x, RAY_X, y))
continue;
cast(u, x, y);
pushstk(u->rson);
pushstk(u->lson);
}
}
} mbrh;
int main() {
int n, m, cmd, x, pos;
double px, py;
scanf("%d %d", &n, &m);
mesh.read(n);
mlist.init(), mbrh.init();
for (int i = 0; i < m; i++) {
scanf("%d", &cmd);
if (cmd == 1) {
scanf("%d %d", &x, &pos);
mbrh.insert(mlist.insert(x, pos));
} else if (cmd == 2) {
scanf("%d", &x);
mbrh.remove(mlist.remove(x));
} else {
scanf("%lf %lf", &px, &py);
puts(mbrh.inside(px, py) ? "1" : "0");
}
}
return 0;
}
Read More +

動態樹 樹形避難所

題目描述請至 Zerojudge e003: 樹形避難所 I、e004: 樹形避難所 II 查閱詳細內容

樹形避難所 I

在一個樹形避難所中有 $N$ 個房間,待在充滿監視器房間的你,透過監視器的顯示發現存在一些未知的入侵者出現在某些房間。為了保護同伴,你可以選擇開啟或關閉房間之間的通道,而你也會收到來自於某個房間的同伴求救訊號,此時給予所有可能遇見的入侵者數量,以便同伴做好萬全的作戰準備。然而,操縱通道的控制器已不受限制,你只能眼睜睜地看著同伴與入侵者對抗,現在的你 … 做好準備了嗎?

  • 操作 1 $u$ $v$:將房間 $u$$v$ 的通道開啟
  • 操作 2 $u$ $v$:將房間 $u$$v$ 的通道關閉
  • 操作 3 $u$ $w$:更正房間 $u$$w$ 個入侵者
  • 操作 4 $u$:回答來自 $u$ 的求救信號,告知與其可能面臨到的入侵者個數

樹形避難所 II

由於上一個樹形避難所已經不再安全,全員轉移到下一個避難所,新的地方將不再是先前的平面構造,新的避難所建構在地下水層中,每一個房間可以在水中移動,並且打通到上一層的某一個房間。不幸地,新的入侵者更加地難纏,想保護大家的你,想藉由破壞某一個房間,將其相連的下層房間的入侵者一同殲滅,情局不斷地變化,哪一個才是最好的破壞手段呢 …

  • 操作 1 $u$ $v$:將房間 $u$ 與上層房間 $v$ 的通道開啟
  • 操作 2 $u$:關閉房間 $u$ 與上層的通道
  • 操作 3 $u$ $w$:更正房間 $u$$w$ 個入侵者
  • 操作 4 $u$:估算摧毀房間 $u$,可以殲滅的入侵者個數

分析

這一題對於樹的操作,牽涉到修改邊,修改點權,詢問整個連通的樹大小、以及子樹大小。可以考慮使用 Link/Cut Tree 完成。也有高手使用了離線算法,對操作分治後計算答案,將一個邊的存在時間記錄在某個時間戳記上,整體落在 $\mathcal{O}(M \log M)$,由上而下合併所有存在的邊來完成單一詢問,需要搭配啟發式合併,來指查找根造成的退化,這一點相當地聰明。若強制在線,仍需要使用動態樹完成之。

對於第一題,只有包含前三個操作,可以當作一個無根樹操作,因此在 LCT 中的 $\text{MakeRoot}$ 打上反轉標記,無視原本的父子關係,額外維護一個虛邊上的子樹大小,如此一來就可以計算整個子樹大小。其餘的點權修改就相較於容易許多。對於第二題,便要求有根樹,因此在轉到根節點時,不能打上反轉標記,此時的左子樹為父節點,扣除掉父節點的大小後,便可以得到子樹大小。

  • 動態樹解法:空間複雜度 $\mathcal{O}(N)$,操作複雜度 $\text{Amortized} \; \mathcal{O}(\log N)$
  • 離線解法:空間複雜度 $\mathcal{O}(M \log M)$,整體時間複雜度 $\mathcal{O}(M \log M)$

延伸問題

如果子樹存在等價關係,意即他們會被一個操作同時受到影響,那麼更新會退化嗎?

如果這個問題能被解決,那麼使用相同的概念,便能解決更多的高壓縮架構問題。工作就能輕鬆一些了。

參考解答

樹形避難所 I

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include <bits/stdc++.h>
using namespace std;
class LCT { // Link-Cut Tree
public:
static const int MAXN = 30005;
struct Node;
static Node *EMPTY;
static Node _mem[MAXN];
static int bufIdx;
struct Node {
Node *ch[2], *fa;
int rev;
int vsize, size, val;
void init() {
ch[0] = ch[1] = fa = NULL;
size = 0, vsize = 0, rev = 0;
}
bool is_root() {
return fa->ch[0] != this && fa->ch[1] != this;
}
void pushdown() {
if (rev) {
ch[0]->rev ^= 1;
ch[1]->rev ^= 1;
swap(ch[0], ch[1]);
rev = 0;
}
}
void pushup() {
if (this == EMPTY)
return;
size = ch[0]->size + ch[1]->size + val + vsize;
}
};
LCT() {
EMPTY = &_mem[0];
EMPTY->fa = EMPTY->ch[0] = EMPTY->ch[1] = EMPTY;
EMPTY->size = 0;
bufIdx = 1;
}
void init() {
bufIdx = 1;
}
Node* newNode() {
Node *u = &_mem[bufIdx++];
u->init();
u->fa = u->ch[0] = u->ch[1] = EMPTY;
return u;
}
void rotate(Node *x) {
Node *y;
int d;
y = x->fa, d = y->ch[1] == x ? 1 : 0;
x->ch[d^1]->fa = y, y->ch[d] = x->ch[d^1];
x->ch[d^1] = y;
if (!y->is_root())
y->fa->ch[y->fa->ch[1] == y] = x;
x->fa = y->fa, y->fa = x;
y->pushup(), x->pushup();
}
void deal(Node *x) {
if (!x->is_root()) deal(x->fa);
x->pushdown();
}
void splay(Node *x) {
Node *y, *z;
deal(x);
while (!x->is_root()) {
y = x->fa, z = y->fa;
if (!y->is_root()) {
if (y->ch[0] == x ^ z->ch[0] == y)
rotate(x);
else
rotate(y);
}
rotate(x);
}
x->pushdown();
}
Node* access(Node *u) {
Node *v = EMPTY;
for (; u != EMPTY; u = u->fa) {
splay(u);
u->vsize += u->ch[1] != EMPTY ? u->ch[1]->size : 0;
u->vsize -= v != EMPTY ? v->size : 0;
u->ch[1] = v;
u->pushup();
v = u;
}
return v;
}
void mk_root(Node *u) {
access(u)->rev ^= 1, splay(u);
}
void cut(Node *x, Node *y) {
mk_root(x);
access(y), splay(y);
// debug(10);
assert(y->ch[0] == x);
y->ch[0] = x->fa = EMPTY;
y->pushup();
}
void link(Node *x, Node *y) {
mk_root(y);
access(x), splay(x);
y->fa = x;
x->vsize += y->size;
x->pushup();
}
Node* find(Node *x) {
access(x), splay(x);
for (; x->ch[0] != EMPTY; x = x->ch[0]);
return x;
}
void set(Node *x, int val) {
mk_root(x);
x->val = val;
x->pushup();
}
int get(Node *u) {
mk_root(u);
return u->size;
}
int same(Node *x, Node *y) {
return find(x) == find(y);
}
void debug(int n) {
return;
puts("==================");
for (int i = 1; i <= n; i++) {
Node *u = &_mem[i];
printf("[%d] %d, %d %d, %d %d %d\n", i, u->fa-_mem, u->ch[0]-_mem, u->ch[1]-_mem, u->size, u->vsize, u->val);
}
}
} lct;
LCT::Node *LCT::EMPTY, LCT::_mem[LCT::MAXN];
int LCT::bufIdx;
LCT::Node *node[LCT::MAXN];
int main() {
int n, m;
while (scanf("%d %d", &n, &m) == 2) {
lct.init();
int cmd, u, v, w;
for (int i = 1; i <= n; i++) {
scanf("%d", &w);
node[i] = lct.newNode();
lct.set(node[i], w);
}
for (int i = 0; i < m; i++) {
scanf("%d", &cmd);
if (cmd == 1) {
scanf("%d %d", &u, &v);
lct.link(node[u], node[v]);
} else if (cmd == 2) {
scanf("%d %d", &u, &v);
lct.cut(node[u], node[v]);
} else if (cmd == 3) {
scanf("%d %d", &u, &w);
lct.set(node[u], w);
} else if (cmd == 4) {
scanf("%d", &u);
int p = lct.get(node[u]);
printf("%d\n", p);
} else {
scanf("%d %d", &u, &v);
int f = lct.same(node[u], node[v]);
printf("%d\n", f);
}
lct.debug(10);
}
}
return 0;
}

樹形避難所 II

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include <bits/stdc++.h>
using namespace std;
class LCT { // Link-Cut Tree
public:
static const int MAXN = 30005;
struct Node;
static Node *EMPTY;
static Node _mem[MAXN];
static int bufIdx;
struct Node {
Node *ch[2], *fa;
int vsize, size, val;
void init() {
ch[0] = ch[1] = fa = NULL;
size = 0, vsize = 0;
}
bool is_root() {
return fa->ch[0] != this && fa->ch[1] != this;
}
void pushdown() {
}
void pushup() {
if (this == EMPTY)
return;
size = ch[0]->size + ch[1]->size + val + vsize;
}
};
LCT() {
EMPTY = &_mem[0];
EMPTY->fa = EMPTY->ch[0] = EMPTY->ch[1] = EMPTY;
EMPTY->size = 0;
bufIdx = 1;
}
void init() {
bufIdx = 1;
}
Node* newNode() {
Node *u = &_mem[bufIdx++];
u->init();
u->fa = u->ch[0] = u->ch[1] = EMPTY;
return u;
}
void rotate(Node *x) {
Node *y;
int d;
y = x->fa, d = y->ch[1] == x ? 1 : 0;
x->ch[d^1]->fa = y, y->ch[d] = x->ch[d^1];
x->ch[d^1] = y;
if (!y->is_root())
y->fa->ch[y->fa->ch[1] == y] = x;
x->fa = y->fa, y->fa = x;
y->pushup(), x->pushup();
}
void deal(Node *x) {
if (!x->is_root()) deal(x->fa);
x->pushdown();
}
void splay(Node *x) {
Node *y, *z;
deal(x);
while (!x->is_root()) {
y = x->fa, z = y->fa;
if (!y->is_root()) {
if (y->ch[0] == x ^ z->ch[0] == y)
rotate(x);
else
rotate(y);
}
rotate(x);
}
x->pushdown();
}
Node* access(Node *u) {
Node *v = EMPTY;
for (; u != EMPTY; u = u->fa) {
splay(u);
u->vsize += u->ch[1] != EMPTY ? u->ch[1]->size : 0;
u->vsize -= v != EMPTY ? v->size : 0;
u->ch[1] = v;
u->pushup();
v = u;
}
return v;
}
void mk_root(Node *u) {
access(u), splay(u);
}
void cut(Node *x) {
access(x), splay(x);
x->ch[0]->fa = EMPTY;
x->ch[0] = EMPTY;
x->pushup();
}
void link(Node *x, Node *y) {
access(x), splay(x);
access(y), splay(y);
x->fa = y;
y->vsize += x->size;
y->pushup();
}
Node* find(Node *x) {
access(x), splay(x);
for (; x->ch[0] != EMPTY; x = x->ch[0]);
return x;
}
void set(Node *x, int val) {
mk_root(x);
x->val = val;
x->pushup();
}
int get(Node *u) {
mk_root(u);
int ret = u->size;
if (u->ch[0] != EMPTY)
ret -= u->ch[0]->size;
return ret;
}
int same(Node *x, Node *y) {
return find(x) == find(y);
}
void debug(int n) {
return;
puts("==================");
for (int i = 1; i <= n; i++) {
Node *u = &_mem[i];
printf("[%d] %d, %d %d, %d %d %d\n", i, u->fa-_mem, u->ch[0]-_mem, u->ch[1]-_mem, u->size, u->vsize, u->val);
}
}
} lct;
LCT::Node *LCT::EMPTY, LCT::_mem[LCT::MAXN];
int LCT::bufIdx;
LCT::Node *node[LCT::MAXN];
int main() {
int n, m;
while (scanf("%d %d", &n, &m) == 2) {
lct.init();
int cmd, u, v, w;
for (int i = 1; i <= n; i++) {
scanf("%d", &w);
node[i] = lct.newNode();
lct.set(node[i], w);
}
for (int i = 0; i < m; i++) {
scanf("%d", &cmd);
if (cmd == 1) {
scanf("%d %d", &u, &v);
lct.link(node[u], node[v]);
} else if (cmd == 2) {
scanf("%d", &u);
lct.cut(node[u]);
} else if (cmd == 3) {
scanf("%d %d", &u, &w);
lct.set(node[u], w);
} else if (cmd == 4) {
scanf("%d", &u);
int p = lct.get(node[u]);
printf("%d\n", p);
} else {
scanf("%d %d", &u, &v);
int f = lct.same(node[u], node[v]);
printf("%d\n", f);
}
lct.debug(4);
}
}
return 0;
}
Read More +

波士頓出差 Cadence, Boston

旅程前言

在碩二實習的時候,有碰到一次到美國波士頓出差的機會,有礙於那時候還是實習且研究生的身分,並沒有與團隊一起去。要是出國消失一周的話,指導教授大概會震怒吧,說不定就沒機會出現在 Cadence。

在 2016 那時,台灣的團隊才成立約一年,所以旅程的目的在於去學習,基本上就是產品架構的設計細節與概念、產品開發的流程。即使跟著去那兒,英文聽說都很糟糕的我,也只能看著投影片發呆吧。在這兩年中,團隊從四個人到七個人的成長,產品開發的控制越來越多到台灣團隊手上。因此,此行目的便不再是學習,要探討未來的發展和一些議題。

在出發之前,整理近幾個月的開發議題,手上有兩個舊有產品 OrbitIO 和 Allegro,修改了大幅度的效能問題,但舊有設計架構問題導致一些加速算法無法相容,光是想著這些設計問題,就不知道要怎麼與那邊的團隊討論,這些都是改動十幾年前的設計,我想代碼大多都朝著只增不減的方向邁進,這些問題很少人願意去著手,要去改那些需要十足的勇氣。然後,莫名其妙被加入了 Mission BraveHeart (任務代號:勇敢的心),成功便成英雄。

另一個新產品的開發便是這次出發的壓軸,其內容跟公司的 EDM (Engineering Data Management) 產品有著異曲同工之妙,這困擾了我好幾個月,其概念就是強化版的批改娘,最大的不同在於多人協作的平台,要如何做得簡單好用「Simple is Better Than Complex」。

「我要做些什麼」-《昴宿七星》

新產品的開發耗時將近一年,途中不斷地有新的工作要做,所以在好幾個產品跳來跳去。在 Java, C, Python, Javascript, HTML 跳來跳去,精神都快要達到臨界點。由於需求調整,一路上重新構造了好幾次架構,不斷地懷疑自己到底能不能把這個產品拉出來。由於公司與 DARPA (Defense Advanced Research Projects Agency, 國防高等研究計劃署)
的合作計畫,加速了這一個產品開發,在九月多時輪廓總算釐清了,目標在一個多月內把產品最低需求完成。

很多 EDA Tools 都經歷了好幾年的開發,如 OrbitIO 和 Allegro 更是幾十年的產品,支線需求直接在平台上開發比較沒什麼壓力。這次則要完全跳離所有依賴關係,團隊成員中沒有系統架構的經驗,而我這種半吊子只寫過一點點的網站,一點點的系統,一次就要走這麼遠,壓力不容小覷,這一段日子裡都不怎麼好睡。

「感覺我好像越來越不行了」-《青春豬頭少年不會夢到兔女郎學姊》

隔了一個多月,我們做到了嗎?做到哪裡?

開發過程中一直想找人來幫忙,面了一些高手,但面試的標準無從根據,導致錄取的進展不斷延後,於是先下定決心自己來吧,網頁後台各種從零開始,著手架構好的後台與前端網頁,試圖完成像 Github 與 git 這等偉大的目標。急急忙忙地切分模組出來給小夥伴開發,過程中又不斷地與其他成員說明系統的架構朝什麼發展,甚至一連開了整天的會議說明方向。

出發前一周仍然在調整各個模組的名稱,好讓介紹時快速切入要領。不得不佩服同事們的合作,介紹這方面的能力從以前開始都倚靠著別人,終於準備好上路了。

「這個世界,沒有我的容身之地」-《異世界魔王與召喚少女的奴隸魔術》

啟程須知

給第二次出國的我 (第一次出國在泰國比賽)

礙於研發替代役的角色,出發前到外交部領事事務局申辦護照,不再是以前的三年版本,一次到手十年期限的護照。除了要額外帶著役男身分證外,其餘項目皆與一般申請護照無異,只需要一周的工作天,便可以領取護照。接著拿到新的護照,便向公司的 HR 發出出差申請,附上護照明細與旅途時間,通過後大約在一天左右,就可以從役政署的研發替代役網站列印許可通知書。接著,入境美國申請 ESTA,線上填妥細節繳費,列印好拿著這些就可以入境美國。

若需要國外駕車,可額外申請國際駕照,直接拿汽車駕照去監理站換發就好。不過國外租車的額外駕駛需要額外的保險,加一個額外駕駛就額外多一個費用,原則上對於我這種新手,最後沒有用到。

十一月初的波士頓到了將近攝氏零度的氣候,這一次旅程長達十四天,差不多要帶個六天的衣物,由於這麼冷的天氣基本上也不太需要太多外衣,內衣之類的還是需要帶多一點,直接在旅館內乾洗晾乾就好,大部分時間都有暖氣,所以只需要帶一件足夠厚的外套就行,也因為暖氣會不斷地除溼,保濕乳液之類的必須帶好。這次旅程意外地發現自己並不太怕冷,帶太多衣服穿不到,感覺有點傻了,毛襪不帶也沒關係,穿了反而不帶適應走路的步伐而不舒服。圍巾、手套帶著比較好,一下雪整個寒意就透過去。

波士頓之旅

做了近 20 小時的飛機,終於到了美國波士頓,公司在比較偏遠的郊區 Chelmsford,隔天我們便到波士頓市中心附近的 MIT 和 Harvard 參觀,這時間點在感恩節前兩周,又正值假日,基本上都沒什麼學生。看著別人的生活環境,冷到一個很不舒服的季節。

MIT

在市中心晃了好一陣子,傍晚才前往到哈佛大學,然後開始排隊與那個金鞋合照。

Harvard University

工作的第一天,聽著不太明白的產品與客戶發展介紹,第一次與 email 對面的人碰面聊天,上頭的上頭們全都來了,勉勉強強用殘破的英文亂說一通,還好有同事罩著,後面講的介紹一句也不懂,只能東猜猜西猜猜,猜出個什麼來再應付。下午便在討論「勇敢的心」細節,原則上是一個複雜度很難壓低的幾何計算,咱什麼時候變成幾何計算的顧問了?我其實也不算懂啊。

工作的第二天,兵分兩路被拆開到各自的主攻產品討論議題,陸陸續續邀請不同議題的相關成員會面,個人覺得是相當大的陣仗,區區的 Morris 開的議題邀了好幾個不同團隊的成員。由當地的同事主持會議,大多的時間都在聽他們討論,只花了幾分鐘介紹問題的原因、要解決的問題、可能的解決方向,為何需要這麼做?接著的應答就靠神一般同事翻譯。嗚嗚,我好沒用。晚上的時候,波士頓的第一場雪來了。

First Snow in Chelmsford

工作的第三天,新產品決鬥的開始,Made in Taiwan 的武力展示,相當沒有信心去展示那些成果,大部分的架構還不確定能不能發展到那樣子,語言的特性決定發展能力,簡單、好用是否能兩全其美呢,覺得自己的眼界還不夠寬廣,深怕被那些非常非常資深的工程師擊飛,最後倖存!

工作的第四天,趕上公司的三十周年慶,公司租了一台遊艇在波士頓河岸繞了兩個小時,各個同事都在船上閒聊。結果我們台灣的都在玩船外的 table football 而忘了拍團體照 …

Cadence 30th Celebration

工作的第五天,討論要怎麼解決大數據的情況,數據一大只要會動就好,那麼效能就不再重要,但是舊有的操作又不能太慢,毫無用武之地的我,決定來個幻想之旅。最後一晚的聚餐,照片上的兇手替我點了 50 美元的龍蝦,看不懂菜單總是令人宰割。

$50 Lobster

紐約之旅

在忙完一周的工作後,我們便到了第二周的紐約自由行。老實說,一開始的行程是回台灣休息,但是大部分的人都不在台灣,如果回台灣也處於無同事或目標的狀況,所以就跟著跑去紐約了。如此瘋狂的行程,大概就這一次!

「我真的沒有想做的事啊」-《來自繽紛世界的明日》

Read More +

UVa 12254 - Electricity Connection

Problem

給一個 $8 \times 8$ 平面圖,上面至多有八個住家,我們目標要從發電廠出發,牽電到所有的住家,拉線跨過水路的花費 $pw$、一般陸路為 $pl$,求最少花費。

經典的斯坦納樹問題,但有別於一般的平面圖,使用歐基里德距離或者曼哈頓距離作為花費函數。接著讓我們細談如何進行常數優化。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
0 10
H.W.WH..
..W.W...
..WGW...
........
........
........
........
........
0 0
H.W.WH..
..W.W...
..WGW...
........
........
........
........
........

Sample Output

1
2
Case 1: 12
Case 2: 7

Solution

斯坦納樹為 NP-hard 問題,因此沒有多項式解法,而要得到確切的最小化解,則必須透過動態規劃來完成。由於題目給定的範圍很小,首先將目標要連通完成的點集,壓縮成 $N$ 個位元,接著紀錄這個聯通元件的其中一個節點視為根。最後,得到狀態數為 $M \cdot 2^N$,可以參考 《「Steiner tree problem in graphs」斯坦納樹》 -日月卦長 的說明。

公式可以拆成兩種情況,第一種為從子集合併中著手,另一種為拓展連通元件 (替換根節點,但不改變目前已經連到的目標集合)。定義 dp[s][i] 為根 i,連通集合 s 的最小花費

  • $dp[S][i] = \min(dp[T][j]+dp[S−T][j]+\text{dist}(i, j):j \in V,T \subset S)$
  • $dp[S][i] = \min(dp[S][k] + \text{dist}(S, k))$

由上述的公式,我們便可知道複雜度為 $O(M \cdot 3^N)$

實作細節

  • 對於內存布局,有兩個選擇 dp[2^N][M] 或者是 dp[M][2^N],其中以 dp[2^N][M] 最為適合,在撰寫迴圈的時候,最內層的迴圈為替換根,這麼一來 cache miss 的機會就非常低。更容易透過 unroll loop 和向量化來運作。

    • 如果內存布局使用 dp[M][2^N],在撰寫向量化時,需要使用 gather 相關的指令,這部分只有在 AVX2 有,並不是每一個 online judge 都支援,而 latency 也算挺高的,等到哪天 CPU 架構換了,這解法可能才會快得起來。
  • 當我們窮舉子集合時,發現到公式有對稱性,便可只窮舉上半部。這樣可以加速 20% 的效能。

1
2
3
4
5
6
7
8
9
10
for (int i = 1, h; i < (1<<n); i++) {
if ((i&(-i)) == i)
h = i-1;
for (int k = (i-1)&i; k > h; k = (k-1)&i) {
for (int j = 0; j < 64; j++)
dp[i][j] = min(dp[i][j], dp[k][j]+dp[i^k][j]-w[j]);
}
relax(i);
}

基礎篇

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
#pragma GCC target("avx")
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
char g[8][16], w[64];
static const int dx[] = {0, 0, 1, -1};
static const int dy[] = {1, -1, 0, 0};
static int32_t dp[1<<8][64];
const int INF = 0x3f3f3f3f;
void relax(int s) {
static int8_t Q[1024];
uint64_t inq = 0;
int Qn = 0;
for (int i = 0; i < 64; i++) {
if (dp[s][i] != INF)
Q[Qn++] = i, inq |= 1ULL<<i;
}
for (int i = 0; i < Qn; i++) {
int u = Q[i];
int x = u>>3, y = u&7;
inq ^= 1ULL<<u;
for (int k = 0; k < 4; k++) {
int tx = x+dx[k], ty = y+dy[k];
if (tx < 0 || ty < 0 || tx >= 8 || ty >= 8)
continue;
int v = tx<<3|ty;
if (dp[s][v] > dp[s][u]+1+w[v]) {
dp[s][v] = dp[s][u]+1+w[v];
if (((inq>>v)&1) == 0) {
inq |= 1ULL<<v;
Q[Qn++] = v;
}
}
}
}
}
int main() {
int testcase, cases = 0;
int pl, pw;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d %d", &pl, &pw);
for (int i = 0; i < 8; i++)
scanf("%s", &g[i]);
int n = 0, root = 0;
int A[8];
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
int u = i<<3|j;
if (g[i][j] == 'H')
A[n++] = u, w[u] = 0;
else if (g[i][j] == 'G')
w[u] = 0, root = u;
else if (g[i][j] == 'W')
w[u] = pw;
else if (g[i][j] == '.')
w[u] = pl;
}
}
memset(dp, 0x3f, sizeof(dp));
for (int i = 0; i < n; i++)
dp[1<<i][A[i]] = 0;
for (int i = 1, h; i < (1<<n); i++) {
if ((i&(-i)) == i)
h = i-1;
for (int k = (i-1)&i; k > h; k = (k-1)&i) {
for (int j = 0; j < 64; j++)
dp[i][j] = min(dp[i][j], dp[k][j]+dp[i^k][j]-w[j]);
}
relax(i);
}
int ret = dp[(1<<n)-1][root];
printf("Case %d: %d\n", ++cases, ret);
}
return 0;
}

SSE 向量化

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
#pragma GCC target("avx")
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#include <x86intrin.h>
using namespace std;
char g[8][16];
static const int dx[] = {0, 0, 1, -1};
static const int dy[] = {1, -1, 0, 0};
static int32_t w[64] __attribute__ ((aligned(16)));
static int32_t dp[1<<8][64] __attribute__ ((aligned(16)));
const int INF = 0x3f3f3f3f;
void relax(int s) {
static int8_t Q[1024];
uint64_t inq = 0;
int Qn = 0;
for (int i = 0; i < 64; i++) {
if (dp[s][i] != INF)
Q[Qn++] = i, inq |= 1ULL<<i;
}
for (int i = 0; i < Qn; i++) {
int u = Q[i];
int x = u>>3, y = u&7;
inq ^= 1ULL<<u;
for (int k = 0; k < 4; k++) {
int tx = x+dx[k], ty = y+dy[k];
if (tx < 0 || ty < 0 || tx >= 8 || ty >= 8)
continue;
int v = tx<<3|ty;
if (dp[s][v] > dp[s][u]+1+w[v]) {
dp[s][v] = dp[s][u]+1+w[v];
if (((inq>>v)&1) == 0) {
inq |= 1ULL<<v;
Q[Qn++] = v;
}
}
}
}
}
int main() {
int testcase, cases = 0;
int pl, pw;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d %d", &pl, &pw);
for (int i = 0; i < 8; i++)
scanf("%s", &g[i]);
int n = 0, root = 0;
int A[8];
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
int u = i<<3|j;
if (g[i][j] == 'H')
A[n++] = u, w[u] = 0;
else if (g[i][j] == 'G')
w[u] = 0, root = u;
else if (g[i][j] == 'W')
w[u] = pw;
else if (g[i][j] == '.')
w[u] = pl;
}
}
memset(dp, 0x3f, sizeof(dp));
for (int i = 0; i < n; i++)
dp[1<<i][A[i]] = 0;
for (int i = 1, h; i < (1<<n); i++) {
if ((i&(-i)) == i)
h = i-1;
for (int k = (i-1)&i; k > h; k = (k-1)&i) {
for (int j = 0; j+4 <= 64; j += 4) {
__m128i mv = _mm_load_si128((__m128i*) (dp[i]+j));
__m128i a = _mm_load_si128((__m128i*) (dp[k]+j));
__m128i b = _mm_load_si128((__m128i*) (dp[i^k]+j));
__m128i tm = _mm_add_epi32(a, b);
__m128i c = _mm_load_si128((__m128i*) (w+j));
__m128i tn = _mm_sub_epi32(tm, c);
__m128i mn = _mm_min_epi32(mv, tn);
_mm_store_si128((__m128i*) (dp[i]+j), mn);
}
// dp[i][j] = min(dp[i][j], dp[k][j]+dp[i^k][j]-w[j]);
}
relax(i);
}
int ret = dp[(1<<n)-1][root];
printf("Case %d: %d\n", ++cases, ret);
}
return 0;
}

AVX2 Gather

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
/*
It doesn't work at UVA 2018/08/13 because server CPU does not support
AVX2 instruction set. Although we could pass the compiler, you still
get runtime error during executing an illegal instruction.
*/
#pragma GCC target("avx")
#pragma GCC target("avx2")
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#include <x86intrin.h>
#include <avx2intrin.h>
using namespace std;
char g[8][16], w[64];
static const int dx[] = {0, 0, 1, -1};
static const int dy[] = {1, -1, 0, 0};
static int32_t dp[64][1<<8] __attribute__ ((aligned(16)));
const int INF = 0x3f3f3f3f;
void relax(int s) {
static int8_t Q[1024];
uint64_t inq = 0;
int Qn = 0;
for (int i = 0; i < 64; i++) {
if (dp[i][s] != INF)
Q[Qn++] = i, inq |= 1ULL<<i;
}
for (int i = 0; i < Qn; i++) {
int u = Q[i];
int x = u>>3, y = u&7;
inq ^= 1ULL<<u;
for (int k = 0; k < 4; k++) {
int tx = x+dx[k], ty = y+dy[k];
if (tx < 0 || ty < 0 || tx >= 8 || ty >= 8)
continue;
int v = tx<<3|ty;
if (dp[v][s] > dp[u][s]+1+w[v]) {
dp[v][s] = dp[u][s]+1+w[v];
if (((inq>>v)&1) == 0) {
inq |= 1ULL<<v;
Q[Qn++] = v;
}
}
}
}
}
int main() {
int testcase, cases = 0;
int pl, pw;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d %d", &pl, &pw);
for (int i = 0; i < 8; i++)
scanf("%s", &g[i]);
int n = 0, root = 0;
int A[8];
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
int u = i<<3|j;
if (g[i][j] == 'H')
A[n++] = u, w[u] = 0;
else if (g[i][j] == 'G')
w[u] = 0, root = u;
else if (g[i][j] == 'W')
w[u] = pw;
else if (g[i][j] == '.')
w[u] = pl;
}
}
memset(dp, 0x3f, sizeof(dp));
for (int i = 0; i < n; i++)
dp[A[i]][1<<i] = 0;
for (int i = 1, h; i < (1<<n); i++) {
if ((i&(-i)) == i)
h = i-1;
__attribute__ ((aligned(16))) static int subset1[1<<8] = {};
__attribute__ ((aligned(16))) static int subset2[1<<8] = {};
int sn = 0;
for (int k = (i-1)&i; k > h; k = (k-1)&i)
subset1[sn] = k, subset2[sn] = i^k, sn++;
while (sn&4)
subset1[sn] = 0, subset2[sn] = i, sn++;
for (int j = 0; j < 64; j++) {
int32_t mn = dp[j][i]+w[j];
__m128i mv = _mm_setr_epi32(mn, mn, mn, mn);
for (int t = 0; t <= sn; t += 4) {
int k;
__m128i a = _mm_load_si128((__m128i*) subset1+t);
__m128i b = _mm_load_si128((__m128i*) subset2+t);
__m128i t1 = _mm_i32gather_epi32(dp[j], a, 4);
__m128i t2 = _mm_i32gather_epi32(dp[j], b, 4);
__m128i tm = _mm_add_epi32(t1, t2);
mv = _mm_min_epi32(mv, tm);
}
__attribute__ ((aligned(16))) int32_t mr[4];
_mm_store_si128((__m128i*) mr, mv);
mn = min(min(mr[0], mr[1]), min(mr[2], mr[3]));
dp[j][i] = mn-w[j];
// mn = min(mn, dp[j][k]+dp[j][i^k]-ww);
}
relax(i);
}
int ret = dp[root][(1<<n)-1];
printf("Case %d: %d\n", ++cases, ret);
}
return 0;
}
Read More +

優化技巧 - 排序/優先隊列

主要問題

在算法問題中,時常結合到排序,而排序的常數也大大影響到我們整體的效能。

基數排序降低常數

若是一般原始型別的排序,可以透過基數排序 (radix sort)。從排序的範圍來決定是否要劃分 8-bit 一組一組。若範圍介於可容忍的 $[0, v]$,當 $v < n$ 時,直接開 $n$ 個 bucket 的方式更好。因為大多數的複雜度都大於線性 $O(n)$

非負整數基數排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void _radix_sort(Pt *A, int n) {
static Pt _tmp[MAXN];
const int CHUNK = 256;
static int C[CHUNK];
Pt *B = _tmp, *T;
for (int x = 0; x < 8; x++) {
const int d = x*8;
memset(C, 0, sizeof(C));
for (int i = 0; i < n; i++)
C[(A[i].x>>d)&(CHUNK-1)]++;
for (int i = 1; i < CHUNK; i++)
C[i] += C[i-1];
for (int i = n-1; i >= 0; i--)
B[--C[(A[i].x>>d)&(CHUNK-1)]] = A[i];
T = A, A = B, B = T;
}
}

浮點數基數排序

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
void radix_sort(Pt *A, int n) {
for (int i = 0; i < n; i++) {
int32_t &v = *((int32_t *) &(A[i].s));
if ((v>>31)&1)
v = ~v;
else
v = v | 0x80000000;
}
static Pt _tmp[MAXN*2];
static const int CHUNK = 256;
static int C[1<<8];
Pt *B = _tmp, *T;
for (int x = 0; x < 4; x++) {
const int d = x*8;
memset(C, 0, sizeof(C));
for (int i = 0; i < n; i++)
C[((*((int32_t *) &(A[i].s)))>>d)&(CHUNK-1)]++;
for (int i = 1; i < CHUNK; i++)
C[i] += C[i-1];
for (int i = n-1; i >= 0; i--)
B[--C[((*((int32_t *) &(A[i].s)))>>d)&(CHUNK-1)]] = A[i];
T = A, A = B, B = T;
}
for (int i = 0; i < n; i++) {
int32_t &v = *((int32_t *) &(A[i].s));
if ((v>>31)&1)
v = v & 0x7fffffff;
else
v = ~v;
}
}

慎選內建排序

內建排序常見的有 qsort, sort, stable_sort,我不推薦使用 qsort,因為它在很久以前找到了一個退化情況 A Killer Adversary for Quicksort - 1995,有些題目的測資會出這種特別案例,導致當年的萌新內心受創。除非只有 C 的情況,否則請避開 qsort。如果算法屬於調整某些元素後,再對整體進行排序,這時候 sortstable_sort 慢很多。當情況非常接近已經排序的時候,就使用 stable_sort

優先隊列

使用 priority queue 的方法通常有三種 set, priority_queue, heap

  • 功能最多的 set、次少的 priority_queue,最少的 heap
  • 效能方面則是 heap 最快、次著 priority_queue、最後 set
  • 代碼維護最容易的 set、最差的 heap

之前很排斥使用 priority_queue,原因在於撰寫 operator< 與我的邏輯相反,因此都偏愛使用 set,但是效能被拉出來的時候,又必須退回類似 C 的 make_heappop_heap … 的接口。

Read More +

UVa 12310 - Point Location

Problem

給定一平面上 $n$ 個點,接著拉 $m$ 個線段拼湊成不相交的區域,並將標記數個點位置所在的區域。接著有數個詢問「點在哪一個先前標記的同一區域內」。

這一問題常在幾何處理中出現,詳細可查閱 Wikipedia - Point location,在此不額外說明。

Sample Input

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
14 16 5 5
0 0
30 0
40 0
60 0
60 50
0 50
20 40
10 10
30 10
30 20
40 20
50 30
50 40
30 40
1 2
2 9
9 8
8 7
7 9
9 10
10 11
11 3
3 4
4 5
5 6
6 1
12 13
13 14
14 12
2 3
20 20
10 20
35 10
45 39
1 60
28 11
29 14
34 7
40 38
70 1
0 0 0 0

Sample Output

1
2
3
4
5
1
2
3
4
5

Solution

Previously

在大學修計算幾何的時候,知道這一類的題目要透過梯形剖分的方式,搭配的資料結構類似四分樹,分隔的基準是一個線段,將線段兩個端點分別拉出無限延長的垂直線,但這方法對於線段本身是垂直時,處理情況比較複雜,那時構思了好幾天沒個底,只好放棄。現在,在 Cadence 公司上班快滿一年,解決幾何操作不在少數,成長的我應該能解決這一題了吧。

Detail

題目已經保證給予的線段除了端點外,彼此之間不會相交任何一點。便可以對所有線段建立空間分割相關的資料結構,好讓我們對於解決,從詢問點出發往 $y$ 無窮遠的射線,最後會打到哪一個線段。

處理的流程如下:

Step 1. 輸入線段

Step 2. 套上邊界,需要能包含所有詢問點

Step 3. 對每一個相連的線段集合,找出 $y$ 軸最高的點,放出輔助射線

Step 4. 對每一個頂點進行極角排序,進行繞行分組

首先,對於幾何剖分的問題,為處理方便,都會套上一個無限大的外框,把所有頂點包在裡面。你可以透過 GeoGebra 這套數學軟體,將處理過程中的資料丟進去,方便你除錯。如果要批次輸入一大筆,請透過上方的建立按鈕 (Button),將 command 的語法以行為單位放入,語法類似 javascript。

接著,我們需要對每一個線段集合的最高點放出輔助射線 (這部分已經縮減了不少,原則上對每一個頂點放出射線也可以),這些輔助射線用來解決內部的孤立形,要把整個圖串成一個連通圖。否則,當詢問屬於內部的孤立形狀的外部時,我們會缺少足夠的資訊連到包含這個孤立形的外框。

最後,對每一個頂點相連的邊進行極角排序,接著才能決定相鄰的邊,而任兩個相鄰的邊所夾的區域屬於同一個集合,因此我們需要對每一個有方向的邊進行編號,將邊與邊合併到同一個集合。對於每一個詢問,只需要對詢問點放出射線找到接觸的線段,便可以知道所在的集合。

  • 若使用 KD tree,即使交替選擇 $x$-$y$ 軸分割,也沒辦法保證樹高。因為處理的是線段,而不是點,每一次挑選的分隔軸,將會產生三個子樹,中間的子樹為與分隔軸相交的線段。在大部分的情況下,整體時間複雜度落在 $O(n \log n)$,空間複雜度 $O(n)$
  • 若使用線段樹,將在 $x$ 軸上劃分,每一個線段至多被拆成 $O(\log n)$ 個,詢問射線第一個碰觸的線段時,單一詢問的時間複雜度 $O(\log n)$,常數相較於 KD tree 多。整體時間複雜度落在 $O(n \log n)$,空間複雜度 $O(n \log n)$

還有許多 spatial data structure 可以考慮,這裡只挑選兩個出來實驗,上述皆為在線算法。也可以將所有操作離線,這時候將套用掃描線算法,但對於垂直線段如何在算法中維護二元樹,目前遇到一些實作上的問題,這將在未來才能給各位參考。

KD tree

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
#include <bits/stdc++.h>
using namespace std;
const float eps = 1e-6;
const float BOX_MX = 2000000;
struct Pt {
float x, y;
Pt() {}
Pt(float a, float b): x(a), y(b) {}
Pt operator-(const Pt &a) const { return Pt(x - a.x, y - a.y); }
Pt operator+(const Pt &a) const { return Pt(x + a.x, y + a.y); }
Pt operator*(const double a) const { return Pt(x * a, y * a); }
bool operator<(const Pt &a) const {
if (fabs(x - a.x) > eps) return x < a.x;
if (fabs(y - a.y) > eps) return y < a.y;
return false;
}
bool operator==(const Pt &a) const {
return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
}
void println() const {
printf("(%lf, %lf)\n", x, y);
}
};
struct Seg {
Pt s, e;
int i;
Seg() {}
Seg(Pt a, Pt b, int i):s(a), e(b), i(i) {}
void println() {
printf("Segment((%lf, %lf), (%lf, %lf))\n", s.x, s.y, e.x, e.y);
}
};
double dot(Pt a, Pt b) {
return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
int cmpZero(float v) {
if (fabs(v) > eps) return v > 0 ? 1 : -1;
return 0;
}
Pt getIntersect(Seg a, Seg b) {
Pt u = a.s - b.s;
double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
return a.s + (a.e - a.s) * t;
}
struct AngleCmp {
Pt o;
AngleCmp(Pt o = Pt()):o(o) {}
bool operator() (const pair<Pt, int>& ppa, const pair<Pt, int>& ppb) {
Pt pa = ppa.first, pb = ppb.first;
Pt p1 = pa - o, p2 = pb - o;
if (p1.y == 0 && p2.y == 0 && p1.x * p2.x <= 0) return p1.x > p2.x;
if (p1.y == 0 && p1.x >= 0 && p2.y != 0) return true;
if (p2.y == 0 && p2.x >= 0 && p1.y != 0) return false;
if (p1.y * p2.y < 0) return p1.y > p2.y;
double c = cross2(p1, p2);
return c > 0 || (c == 0 && fabs(p1.x) < fabs(p2.x));
}
};
static Pt pts[10005];
static Seg segs[30005];
struct BSP {
static const int MAXN = 60005;
static const int MAXNODE = 60005;
struct Node {
float lx, ly, rx, ry;
Node *ls, *ms, *rs;
void extend(Node *u) {
if (u == NULL)
return ;
lx = min(lx, u->lx), ly = min(ly, u->ly);
rx = max(rx, u->rx), ry = max(ry, u->ry);
}
} nodes[MAXNODE];
int sn[MAXNODE];
Seg *seg[MAXNODE];
float axis[MAXN];
Node *root;
int size;
Node* newNode() {
Node *p = &nodes[size++];
assert(size < MAXNODE);
p->ls = p->ms = p->rs = NULL;
sn[p-nodes] = 0;
return p;
}
Node* _build(int k, Seg segs[], int n) {
if (n == 0)
return NULL;
if (k == 2)
k = 0;
int Lsize = 0, Msize = 0, Rsize = 0;
Seg *L = NULL, *M = NULL, *R = NULL;
if (k == 0) {
for (int i = 0; i < n; i++)
axis[i<<1] = segs[i].s.x, axis[i<<1|1] = segs[i].e.x;
nth_element(axis, axis+n, axis+2*n);
const float mval = axis[n];
L = segs;
R = std::partition(segs, segs+n, [mval](const Seg &s) {
return max(s.s.x, s.e.x) <= mval;
});
M = std::partition(R, segs+n, [mval](const Seg &s) {
return min(s.s.x, s.e.x) <= mval;
});
Msize = segs+n - M;
Rsize = M - R;
Lsize = R - segs;
} else {
for (int i = 0; i < n; i++)
axis[i<<1] = segs[i].s.y, axis[i<<1|1] = segs[i].e.y;
nth_element(axis, axis+n, axis+2*n);
const float mval = axis[n];
L = segs;
R = std::partition(segs, segs+n, [mval](const Seg &s) {
return max(s.s.y, s.e.y) <= mval;
});
M = std::partition(R, segs+n, [mval](const Seg &s) {
return min(s.s.y, s.e.y) <= mval;
});
Msize = segs+n - M;
Rsize = M - R;
Lsize = R - segs;
}
Node *u = newNode();
u->lx = BOX_MX, u->ly = BOX_MX;
u->rx = -BOX_MX, u->ry = -BOX_MX;
if (Lsize == n || Rsize == n || Msize == n) {
sn[u - nodes] = n, seg[u - nodes] = segs;
for (int i = 0; i < n; i++) {
u->lx = min(u->lx, min(segs[i].s.x, segs[i].e.x));
u->rx = max(u->rx, max(segs[i].s.x, segs[i].e.x));
u->ly = min(u->ly, min(segs[i].s.y, segs[i].e.y));
u->ry = max(u->ry, max(segs[i].s.y, segs[i].e.y));
}
} else {
u->ls = _build(k+1, L, Lsize), u->extend(u->ls);
u->ms = _build(k+1, M, Msize), u->extend(u->ms);
u->rs = _build(k+1, R, Rsize), u->extend(u->rs);
}
return u;
}
void build_tree(Seg s[], int m) {
size = 0;
root = _build(0, s, m);
}
Pt q_st, q_ed;
int q_si;
void rayhit(Seg &seg) {
if (seg.s.x == seg.e.x) {
if (cmpZero(seg.s.x - q_st.x) == 0) {
double low = min(seg.s.y, seg.e.y);
if (low > q_st.y && low < q_ed.y) {
q_ed.y = low;
q_si = seg.i;
}
}
return ;
}
if (max(seg.s.x, seg.e.x) < q_st.x || min(seg.s.x, seg.e.x) > q_st.x)
return ;
float y = seg.s.y + (float) (seg.e.y - seg.s.y) * (q_st.x - seg.s.x) / (seg.e.x - seg.s.x);
if (y > q_st.y && y < q_ed.y) {
q_ed.y = y;
q_si = seg.i;
}
}
void search(Node *u) {
if (u == NULL)
return ;
if (u->lx > q_st.x || u->rx < q_st.x || u->ry <= q_st.y || u->ly >= q_ed.y)
return ;
for (int i = 0; i < sn[u - nodes]; i++)
rayhit(seg[u - nodes][i]);
search(u->ls);
search(u->ms);
search(u->rs);
}
pair<int, Pt> raycast(Pt st) {
q_st = st;
q_ed = Pt(st.x, BOX_MX+1);
q_si = -1;
search(root);
return {q_si, q_ed};
}
} tree;
struct Disjoint {
static const int MAXN = 65536;
uint16_t parent[MAXN], weight[MAXN];
void init(int n) {
if (n >= MAXN)
exit(0);
for (int i = 0; i <= n; i++)
parent[i] = i, weight[i] = 1;
}
int findp(int x) {
return parent[x] == x ? x : parent[x] = findp(parent[x]);
}
int joint(int x, int y) {
x = findp(x), y = findp(y);
if (weight[x] >= weight[y])
parent[y] = x, weight[x] += weight[y];
else
parent[x] = y, weight[y] += weight[x];
}
} egroup, sgroup;
int main() {
int n, m, p, q;
while (scanf("%d %d %d %d", &n, &m, &p, &q) == 4 && n) {
for (int i = 0; i < n; i++) {
int x, y;
scanf("%d %d", &x, &y);
pts[i] = Pt(x, y);
}
sgroup.init(n);
for (int i = 0; i < m; i++) {
int st_i, ed_i;
scanf("%d %d", &st_i, &ed_i);
st_i--, ed_i--;
segs[i] = Seg(pts[st_i], pts[ed_i], i);
sgroup.joint(st_i, ed_i);
}
segs[m] = Seg(Pt(BOX_MX, BOX_MX), Pt(BOX_MX, -BOX_MX), m), m++;
segs[m] = Seg(Pt(BOX_MX, -BOX_MX), Pt(-BOX_MX, -BOX_MX), m), m++;
segs[m] = Seg(Pt(-BOX_MX, -BOX_MX), Pt(-BOX_MX, BOX_MX), m), m++;
segs[m] = Seg(Pt(-BOX_MX, BOX_MX), Pt(BOX_MX, BOX_MX), m), m++;
static map<Pt, vector<pair<Pt, uint8_t>>> g; g.clear();
static vector<vector<Pt>> on_seg; on_seg.clear(); on_seg.resize(m);
for (int i = 0; i < m; i++) {
on_seg[segs[i].i].reserve(4);
on_seg[segs[i].i].push_back(segs[i].s);
on_seg[segs[i].i].push_back(segs[i].e);
}
// for (int i = 0; i < n; i++)
// pts[i].println();
// for (int i = 0; i < m; i++)
// segs[i].println();
tree.build_tree(segs, m);
{
Pt top[10005];
for (int i = 0; i < n; i++)
top[i] = pts[i];
for (int i = 0; i < n; i++) {
int gid = sgroup.findp(i);
if (top[gid].y < pts[i].y)
top[gid] = pts[i];
}
for (int i = 0; i < n; i++) {
if (sgroup.findp(i) != i)
continue;
auto p = top[i];
auto hit = tree.raycast(p);
if (hit.first >= 0) {
on_seg[hit.first].emplace_back(hit.second);
g[p].emplace_back(hit.second, 1);
g[hit.second].emplace_back(p, 1);
}
}
}
for (int i = 0; i < m; i++) {
vector<Pt> &a = on_seg[i];
sort(a.begin(), a.end());
a.resize(unique(a.begin(), a.end()) - a.begin());
auto *prev = &g[a[0]];
for (int j = 1; j < a.size(); j++) {
prev->emplace_back(a[j], 0);
prev = &g[a[j]];
prev->emplace_back(a[j-1], 0);
}
}
for (auto &e : g)
sort(e.second.begin(), e.second.end(), AngleCmp(e.first));
static map<Pt, map<Pt, int>> R; R.clear();
int Rsize = 0;
for (auto &e : g) {
int sz = e.second.size();
map<Pt, int> &Rg = R[e.first];
for (auto &f : e.second) {
int &eid = Rg[f.first];
if (eid == 0)
eid = ++Rsize;
}
}
egroup.init(Rsize);
for (auto &e : g) {
int sz = e.second.size();
map<Pt, int> &Rg = R[e.first];
for (int i = sz-1, j = 0; j < sz; i = j++) {
int l = R[e.second[i].first][e.first];
int r = Rg[e.second[j].first];
egroup.joint(l, r);
if (e.second[i].second != 0) {
r = Rg[e.second[i].first];
assert(l > 0 && r > 0);
egroup.joint(l, r);
}
}
}
for (auto &e : g) {
int sz = e.second.size();
int n = 0;
for (int i = 0; i < sz; i++) {
if (e.second[i].second == 0)
e.second[n++] = e.second[i];
}
e.second.resize(n);
}
static int region[65536]; memset(region, 0, sizeof(0)*Rsize);
for (int i = 0; i < p; i++) {
float x, y;
scanf("%f %f", &x, &y);
pair<int, Pt> hit = tree.raycast(Pt(x, y));
if (hit.first < 0)
continue;
if (g.find(hit.second) != g.end()) {
auto &adj = g[hit.second];
AngleCmp cmp(hit.second);
int pos = 0;
pair<Pt, int> q(Pt(x, y), i+1);
pos = lower_bound(adj.begin(), adj.end(), q, cmp) - adj.begin() - 1;
assert(pos >= 0);
int l = R[adj[pos].first][hit.second];
assert(l > 0);
l = egroup.findp(l);
region[l] = i+1;
} else {
auto &adj = on_seg[hit.first];
Pt lpt = adj[0], rpt = adj[1];
int l;
if (cmpZero(cross(lpt, rpt, Pt(x, y))) <= 0)
l = R[lpt][rpt];
else
l = R[rpt][lpt];
assert(l > 0);
l = egroup.findp(l);
region[l] = i+1;
}
}
for (int i = 0; i < q; i++) {
float x, y;
scanf("%f %f", &x, &y);
pair<int, Pt> hit = tree.raycast(Pt(x, y));
if (hit.first < 0) {
printf("0\n");
continue;
}
if (g.find(hit.second) != g.end()) {
auto &adj = g[hit.second];
AngleCmp cmp(hit.second);
int pos = 0;
pair<Pt, int> q(Pt(x, y), i+1);
pos = lower_bound(adj.begin(), adj.end(), q, cmp) - adj.begin() - 1;
assert(pos >= 0);
int l = R[adj[pos].first][hit.second];
assert(l > 0);
l = egroup.findp(l);
printf("%d\n", region[l]);
} else {
auto &adj = on_seg[hit.first];
Pt lpt = adj[0], rpt = adj[1];
int l;
if (cmpZero(cross(lpt, rpt, Pt(x, y))) <= 0)
l = R[lpt][rpt];
else
l = R[rpt][lpt];
assert(l > 0);
l = egroup.findp(l);
printf("%d\n", region[l]);
}
}
}
return 0;
}

線段樹

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const double BOX_MX = (3000000);
const int AUXID = 200000;
struct Pt {
double x, y;
Pt(double a = 0, double b = 0): x(a), y(b) {}
Pt operator-(const Pt &a) const { return Pt(x - a.x, y - a.y); }
Pt operator+(const Pt &a) const { return Pt(x + a.x, y + a.y); }
Pt operator*(const double a) const { return Pt(x * a, y * a); }
bool operator<(const Pt &a) const {
if (fabs(x - a.x) > eps) return x < a.x;
if (fabs(y - a.y) > eps) return y < a.y;
return false;
}
bool operator==(const Pt &a) const {
return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
}
void println() const {
printf("(%lf, %lf)\n", x, y);
}
};
struct Seg {
Pt s, e;
int i;
Seg() {}
Seg(Pt a, Pt b, int i):s(a), e(b), i(i) {}
void println() const {
printf("Segment((%lf, %lf), (%lf, %lf))\n", s.x, s.y, e.x, e.y);
}
};
double dot(Pt a, Pt b) {
return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double cross2(Pt a, Pt b) {
return a.x * b.y - a.y * b.x;
}
int between(Pt a, Pt b, Pt c) {
return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
int cmpZero(double v) {
if (fabs(v) > eps) return v > 0 ? 1 : -1;
return 0;
}
Pt getIntersect(Seg a, Seg b) {
Pt u = a.s - b.s;
double t = cross2(b.e - b.s, u)/cross2(a.e - a.s, b.e - b.s);
return a.s + (a.e - a.s) * t;
}
struct AngleCmp {
Pt o;
AngleCmp(Pt o = Pt()):o(o) {}
bool operator() (const pair<Pt, int>& ppa, const pair<Pt, int>& ppb) {
Pt pa = ppa.first, pb = ppb.first;
Pt p1 = pa - o, p2 = pb - o;
if (p1.y == 0 && p2.y == 0 && p1.x * p2.x <= 0) return p1.x > p2.x;
if (p1.y == 0 && p1.x >= 0 && p2.y != 0) return true;
if (p2.y == 0 && p2.x >= 0 && p1.y != 0) return false;
if (p1.y * p2.y < 0) return p1.y > p2.y;
double c = cross2(p1, p2);
return c > 0 || (c == 0 && fabs(p1.x) < fabs(p2.x));
}
};
static Pt pts[10005];
static Seg segs[30005];
static double interpolate(const Pt& p1, const Pt& p2, double& x) {
if (cmpZero(p1.x - p2.x) == 0) return min(p1.y, p2.y);
return p1.y + (double)(p2.y - p1.y) / (p2.x - p1.x) * (x - p1.x);
}
struct CMP {
static double x;
bool operator() (const Seg &i, const Seg &j) {
double l = interpolate(i.s, i.e, x);
double r = interpolate(j.s, j.e, x);
return l < r;
}
};
double CMP::x;
struct BSP {
struct Node {
double ly, ry;
void init() {
ly = BOX_MX, ry = -BOX_MX;
}
void extend(Node *u) {
if (u == NULL)
return ;
ly = min(ly, u->ly);
ry = max(ry, u->ry);
}
} bbox[262144];
vector<double> x;
set<Seg, CMP> tree[524288];
Seg segs[262144];
void clear(int k, int l, int r) {
tree[k].clear();
bbox[k].init();
if (l+1 >= r)
return ;
int m = (l+r)/2;
clear(k<<1, l, m);
clear(k<<1|1, m, r);
}
void insert(Seg &s, int k, int l, int r) {
if (s.s.x <= x[l] && x[r] <= s.e.x) {
CMP::x = (x[l] + x[r])/2;
tree[k].insert(s);
double ly = interpolate(s.s, s.e, x[l]);
double ry = interpolate(s.s, s.e, x[r]);
bbox[k].ly = min(bbox[k].ly, min(ly, ry));
bbox[k].ry = max(bbox[k].ry, max(ly, ry));
return ;
}
if (l+1 >= r)
return ;
int m = (l+r)/2;
if (s.s.x <= x[m]) {
insert(s, k<<1, l, m);
bbox[k].extend(&bbox[k<<1]);
}
if (s.e.x > x[m]) {
insert(s, k<<1|1, m, r);
bbox[k].extend(&bbox[k<<1|1]);
}
}
void build_tree(Seg s[], int m) {
memcpy(segs, s, sizeof(segs[0])*m);
x.clear();
for (int i = 0; i < m; i++)
x.push_back(segs[i].s.x), x.push_back(segs[i].e.x);
sort(x.begin(), x.end());
x.resize(unique(x.begin(), x.end()) - x.begin());
clear(1, 0, x.size()-1);
for (int i = 0; i < m; i++) {
if (segs[i].s.x > segs[i].e.x)
swap(segs[i].s, segs[i].e);
if (segs[i].s.x < segs[i].e.x)
insert(segs[i], 1, 0, x.size()-1);
}
}
Pt q_st, q_ed;
int q_si;
void search(int k, int l, int r) {
if (bbox[k].ly >= q_ed.y || bbox[k].ry <= q_st.y)
return ;
if (x[l] <= q_st.x && q_st.x <= x[r]) {
CMP::x = q_st.x;
auto it = tree[k].upper_bound(Seg(q_st, q_st, 0));
while (it != tree[k].end()) {
double y = interpolate(it->s, it->e, CMP::x);
if (y > q_st.y) {
if (y < q_ed.y) {
q_ed.y = y;
q_si = it->i;
}
break;
}
it++;
}
}
if (l+1 >= r)
return ;
int m = (l+r)/2;
if (q_st.x <= x[m])
search(k<<1, l, m);
if (q_st.x >= x[m])
search(k<<1|1, m, r);
}
pair<int, Pt> raycast(Pt st) {
q_st = st;
q_ed = Pt(st.x, BOX_MX+1);
q_si = -1;
search(1, 0, x.size()-1);
return {q_si, q_ed};
}
} tree;
struct Disjoint {
static const int MAXN = 65536;
uint16_t parent[MAXN], weight[MAXN];
void init(int n) {
if (n >= MAXN)
exit(0);
for (int i = 0; i <= n; i++)
parent[i] = i, weight[i] = 1;
}
int findp(int x) {
return parent[x] == x ? x : parent[x] = findp(parent[x]);
}
int joint(int x, int y) {
x = findp(x), y = findp(y);
if (weight[x] >= weight[y])
parent[y] = x, weight[x] += weight[y];
else
parent[x] = y, weight[y] += weight[x];
}
} egroup, sgroup;
int main() {
int n, m, p, q;
while (scanf("%d %d %d %d", &n, &m, &p, &q) == 4 && n) {
for (int i = 0; i < n; i++) {
int x, y;
scanf("%d %d", &x, &y);
pts[i] = Pt(x, y);
}
sgroup.init(n);
for (int i = 0; i < m; i++) {
int st_i, ed_i;
scanf("%d %d", &st_i, &ed_i);
st_i--, ed_i--;
segs[i] = Seg(pts[st_i], pts[ed_i], i);
sgroup.joint(st_i, ed_i);
}
segs[m] = Seg(Pt(BOX_MX, BOX_MX), Pt(BOX_MX, -BOX_MX), m), m++;
segs[m] = Seg(Pt(BOX_MX, -BOX_MX), Pt(-BOX_MX, -BOX_MX), m), m++;
segs[m] = Seg(Pt(-BOX_MX, -BOX_MX), Pt(-BOX_MX, BOX_MX), m), m++;
segs[m] = Seg(Pt(-BOX_MX, BOX_MX), Pt(BOX_MX, BOX_MX), m), m++;
static map<Pt, vector<pair<Pt, uint8_t>>> g; g.clear();
static vector<vector<Pt>> on_seg; on_seg.clear(); on_seg.resize(m);
for (int i = 0; i < m; i++) {
on_seg[segs[i].i].reserve(4);
on_seg[segs[i].i].push_back(segs[i].s);
on_seg[segs[i].i].push_back(segs[i].e);
}
// for (int i = 0; i < n; i++)
// pts[i].println();
// for (int i = 0; i < m; i++)
// segs[i].println();
tree.build_tree(segs, m);
{
Pt top[10005];
for (int i = 0; i < n; i++)
top[i] = pts[i];
for (int i = 0; i < n; i++) {
int gid = sgroup.findp(i);
if (top[gid].y < pts[i].y)
top[gid] = pts[i];
}
for (int i = 0; i < n; i++) {
if (sgroup.findp(i) != i)
continue;
auto p = top[i];
auto hit = tree.raycast(p);
if (hit.first >= 0) {
on_seg[hit.first].emplace_back(hit.second);
g[p].emplace_back(hit.second, 1);
g[hit.second].emplace_back(p, 1);
}
}
}
for (int i = 0; i < m; i++) {
vector<Pt> &a = on_seg[i];
sort(a.begin(), a.end());
a.resize(unique(a.begin(), a.end()) - a.begin());
auto *prev = &g[a[0]];
for (int j = 1; j < a.size(); j++) {
prev->emplace_back(a[j], 0);
prev = &g[a[j]];
prev->emplace_back(a[j-1], 0);
}
}
for (auto &e : g)
sort(e.second.begin(), e.second.end(), AngleCmp(e.first));
static map<Pt, map<Pt, int>> R; R.clear();
int Rsize = 0;
for (auto &e : g) {
int sz = e.second.size();
map<Pt, int> &Rg = R[e.first];
for (auto &f : e.second) {
int &eid = Rg[f.first];
if (eid == 0)
eid = ++Rsize;
}
}
egroup.init(Rsize);
for (auto &e : g) {
int sz = e.second.size();
map<Pt, int> &Rg = R[e.first];
for (int i = sz-1, j = 0; j < sz; i = j++) {
int l = R[e.second[i].first][e.first];
int r = Rg[e.second[j].first];
egroup.joint(l, r);
if (e.second[i].second != 0) {
r = Rg[e.second[i].first];
assert(l > 0 && r > 0);
egroup.joint(l, r);
}
}
}
for (auto &e : g) {
int sz = e.second.size();
int n = 0;
for (int i = 0; i < sz; i++) {
if (e.second[i].second == 0)
e.second[n++] = e.second[i];
}
e.second.resize(n);
}
static int region[65536]; memset(region, 0, sizeof(0)*Rsize);
for (int i = 0; i < p; i++) {
float x, y;
scanf("%f %f", &x, &y);
pair<int, Pt> hit = tree.raycast(Pt(x, y));
if (hit.first < 0)
continue;
if (g.find(hit.second) != g.end()) {
auto &adj = g[hit.second];
AngleCmp cmp(hit.second);
int pos = 0;
pair<Pt, int> q(Pt(x, y), i+1);
pos = lower_bound(adj.begin(), adj.end(), q, cmp) - adj.begin() - 1;
assert(pos >= 0);
int l = R[adj[pos].first][hit.second];
assert(l > 0);
l = egroup.findp(l);
region[l] = i+1;
} else {
auto &adj = on_seg[hit.first];
Pt lpt = adj[0], rpt = adj[1];
int l;
if (cmpZero(cross(lpt, rpt, Pt(x, y))) <= 0)
l = R[lpt][rpt];
else
l = R[rpt][lpt];
assert(l > 0);
l = egroup.findp(l);
region[l] = i+1;
}
}
for (int i = 0; i < q; i++) {
float x, y;
scanf("%f %f", &x, &y);
pair<int, Pt> hit = tree.raycast(Pt(x, y));
if (hit.first < 0) {
printf("0\n");
continue;
}
if (g.find(hit.second) != g.end()) {
auto &adj = g[hit.second];
AngleCmp cmp(hit.second);
int pos = 0;
pair<Pt, int> q(Pt(x, y), i+1);
pos = lower_bound(adj.begin(), adj.end(), q, cmp) - adj.begin() - 1;
assert(pos >= 0);
int l = R[adj[pos].first][hit.second];
assert(l > 0);
l = egroup.findp(l);
printf("%d\n", region[l]);
} else {
auto &adj = on_seg[hit.first];
Pt lpt = adj[0], rpt = adj[1];
int l;
if (cmpZero(cross(lpt, rpt, Pt(x, y))) <= 0)
l = R[lpt][rpt];
else
l = R[rpt][lpt];
assert(l > 0);
l = egroup.findp(l);
printf("%d\n", region[l]);
}
}
}
return 0;
}
Read More +

十二天軍旅生活 (前)

畢業至當兵前

結束研究所離校手續後,便回到家裡等兵單。某方面來說不算等兵單,研發替代役可以上網填入營日期,選擇適合自己的梯次入伍即可。彌補好幾個寒暑假都沒回家的罪過,於是跑去報名汽車駕訓班,沒想到現在學開車外加考照要一個多月,那麼先前填的入伍時間來不及,在確定報名的日期前修改即可,往後延了一個梯次,直到九月中才進去服十二天的新訓。

駕訓班

在這一個多月間,駕訓班平均兩天上一次課,每天排課差不多都是早上八、九點,其中突然有一陣子沒辦法練車,因為有某一梯次的學員要進行考試,好幾天就空著練筆試。上班時期才去學開車也許是個艱難的選項,而我們花蓮的駕訓班排課好像只到晚上六點,想必下班也會來不及。與公司、役政署那邊確定好時間,也要把這一人生階段任務完成。

大家都說以前駕訓班就學手排車,於是一開始學手排車,後來發現對離合器的協調性不足,換自排車繼續學。開了手排車幾堂課,轉換到自排車就覺得相當簡單,自排車比較不會打錯檔位,也許是因為檔位設計的問題吧!哪天教練車高檔一點說不定就好辦了。咱這點自尊先捨棄吧。

不曉得其他駕訓班是怎麼教開車,背口訣打方向盤的圈數、看後照鏡與標線之間的關係,一開始總是憑感覺打方向盤,結果常常被教練說嘴。心想那些口訣換了車就不一樣,而且每個人坐在駕駛坐看到的視角關係也不致相同,我到底該信什麼才好?內心好煎熬啊。

有時開車兩個人輪流開一台車,兩個學員相互看開車的情況,也不知道為什麼幾乎都是女孩子,而且開車技術都還算不錯,像頭文字 D 那般的快速打檔,感覺平常就有開車,坐在一旁都好佩服。後來才發現教練幾乎都帶女生,怪不得安排上都是跟女生居多。開 S 灣的時候壓到線時,當一旁人的一言不發,腦補病患可承受不住的。

直到考試當日,當日早上八點集合帶去監理站考試,筆試背罰金額度的總是相當惱人,那一天死記活拚也弄了個 97.5 分,明明不該是這麼困難的項目,帶著沒拿到滿分的遺憾迎來下午的場內考試。場內考試依舊是各教練分開安排,排隊上車進行測驗,由於監理站人手不足,其他教練評分時仍有全程攝影,待考生坐在後座看前一個考生跑完全程,六十多個人坐在安全島上等待考試。各自帶開後,不出所料這島都是女生,而另一頭都是男生,教練們的合格率賭盤就開始了!不得不說,大部分人都是考自排車,非常少數的人考手排車,大部分上坡起步退場的也都是手排車。

一般而言,大家都以為這樣就結束。「不是的」,像我這種總是可以走到特殊路線的人而言,恰好多了道路駕駛考試,也就是在今年六月開始強制上路的考試,必須在外頭繞一圈合格後才能拿到駕照。好在是在花蓮考試,如果在台北考道路駕駛也許不堪設想。開車出去前要口頭報出車況,我永遠不能明白當初定說要檢查車底的高就在想什麼,要蹲下去看車底高喊「車底無異物」,並且是車子四個方位都要走過去喊,想必在外頭沒有一個人可以做到這一點。為了安全考量看一次,但看到四次只有強迫症患者做得到吧。

說起如何練習道路考試,那是一件很有趣的故事,一般人會想說教練會帶著進行第一次的練習,結果我們教練要求讓家長帶我們去開過一次考試路線,不是家長開給你開,而是你開給家長看。多嚇過幾輪後,教練才會帶你出去練車。然而,礙於其他因素就沒拜託老爸帶我去開。於是-第一次開車上路,沒有經驗的我開車載妹子出去啦,教練還說「把這當載老婆小孩,一句話都不會說,你得一個人開車。」,幸好平安落幕。隨後幾次練車,曾跟著奇葩一起,坐在後頭都會嚇死,教練說道「輕踩壓車減速」,心中吶喊「等等,咱們突然停在路上,停了,真的停了」,原來他沒有騎過機車、腳踏車上路的經驗,當初還以為大家都會騎機車才考汽車,這世界還是很奇妙的。

拉著老爸練了一周的車,考試當天等了三個多小時才輪到最後一個我,坐在前一個考生後頭時,從頭到尾一直在喊「饒了咱吧,快把你的雙手放開,疊在一起放在方向盤上搖來搖去,咱的心臟要受不了」一個急轉彎壓了慢車道過去,全程超速駕駛,考官全程也不能說話,不知道那樣子還算過嗎。等到我開完路線,監考官叫我多開一段路回駕訓班,那時教練們聚著才開始抱怨「現在的年輕人啊…」

老爸拉著我去開台9、台11線,中間繞光豐公路,練習在山路上轉方向盤,開車還要閃遊覽車之類的驚悚橋段,一旁就是山溝,還有道路坍方的單向道,想起來還是得再多多加強。要練到開山路不踩剎車,再開始載人?

練身體

雖然這年頭研發替代役只有十二天的新訓,人生這一階段還是練練身體。每天下午跑去附近公園跑個六、七圈,順便拉著老爸去運動。

覺得慢跑的最重要因素還是腿部和腰部肌肉。高中時間肥到 76kg 時,跑個 1600m 都覺得辛苦,剛上大學覺得自己是個一無是處廢物,大一的生活就有固定跑到宿舍旁邊的操場運動,「因為太廢了,這八圈是懲罰」
。然而,轉學後就一陣子沒運動,直到大三開始跟轉學生學長一起住,瘋了才去跑校園兩圈練半半馬 10km,後來還真的跑去參加半半馬,一個人在人群中擠來擠去。但上了研究所兩年完全沒運動過,每天走三十分鐘往返學校而已。突然跑起 3000m 還是很刺激的,調個一周才讓大腿適應。

後來被老爸抓去花蓮太平洋公園旁的道路跑步,第一次在下午三點太陽正熱,即使有海風吹著跑起來還是相當折磨,單程約有 2km,來回跑就有四公里多,在海邊跑步如此現充?不對,觀光客騎腳踏車、機車超輕鬆的從你旁邊呼嘯而過,而你只有看著狹長的海岸線估算要以何種步伐才得以抵達盡頭的份。

Read More +

吶,還記得我們的「約定」嗎

長途跋涉

碩二下的剩餘幾個月裡,一般情況在口試前一個月開始把實驗補齊,前一週才把論文寫完,隨後口試完,再花個兩三週把論文丟到圖書館後離校,以上是一般碩士生的的常態生活,而我可能就有一點特別。碩二上學期結束時把論文概要想完,過年把中文論文寫個草稿,下學期便耗費數幾個月與老師來來回回地改了好幾輪,一下子就來到了學期結束。

「長篇化就拜託你了」-《情色漫畫老師》

不得不說,內容改了好幾個月,把一些不太想說明、為什麼要說的部分釐清變得相當困難,大部分不想說明的內容、晦暗不明的語句依依剝離出來,反反覆覆地增加了四十幾張圖片,使用 Tikz 這等套件畫圖,可說是相當痛苦得一件事情,一張圖片可能就要花一整個早上來完成。

細節實作的「道理」與其實驗結果,逐一補上「為什麼要這麼做」、「為什麼會快」、「為什麼選用這種方法」諸如此類的問題。在撰寫時只覺得這麼做是對的,感覺上沒有錯,實驗上可以驗證是對的,一被問起來仍是一臉茫然地不知如何說明,還得回去思考到底要怎麼說才能容易明白。

「這不是超過 100 頁了嗎?」-《情色漫畫老師》

一路寫到五月底,而六月初口試的當下,口試現場來了四個教授來聽,相較於學長那時的三人排場的確更盛大點。壓縮簡報內容至一百頁內的投影片,才可能在四十分鐘內講完呢。那些不想細講的內容,在論文裡不說又會被老師要求,口試的時候能不能不說?百感交集下,硬著頭皮一路殺下去講純資料結構和算法的改進,對於一般做計畫而生的論文,我的內容肯定很無趣吧。要是我能強一點就好了。

「要是我能更強就好了」-《夏目友人帳》

講完近一個小時的成果發表,講累的我還一度沒聽懂要開離教室,等待委員商議是否能通過的會議,口試的評分表不知道是以怎麼方式運行,坐在教室外的我焦慮地等待,心想「是不是做的內容有些瑕疵,還是已經有人做過了?還是內容不足以作為一個碩士研究?」

教室那鎖不好的木門聲響起「嘣」一聲,老師從門口向著我說「下去把 XX 一起叫上來」,走下樓把一起口試的同學都叫來教室,才聽到「恭喜你們通過口試」,讀了兩年就等待這一句話,那究竟是怎麼樣的體驗,感覺有點不切實際,就這樣子了?

「這是奇蹟」-《正解的卡多》

儘管已經提早口試,內心再怎麼雀躍,也無法順心地馬上離開這裡,每天依舊來來學校做點雜事,「鈴~鈴~」實驗室電話一響,電話那一頭「有其他人在嗎?那個誰在嗎?麻煩上來一下」,早上十點半的我只能無奈地「誰也不在,現在只有我」,收到「好吧,那你上來」的日常似乎沒有太大的差異。

口試通過後,就該加緊腳步離校了對吧?離校的兩大關卡——口試審定書和離校同意書,過了一關後,還有一關無法通過,那要怎麼通過老師給的離校同意書呢?方法可說是千奇百種啊,男生的最終武器應該是兵單吧,不然總是問最晚什麼時候你才會離開而避開要簽離校,也許還有另一種可能,讓老師覺得「留你也沒用」,幻想著跟老師說「老師啊,就算沒有我,地球也照樣繼續轉,留我做什麼呢?」

「就算沒有我,地球也照樣繼續轉」—《櫻花任務》

六月初那時,別老是問我「為什麼不走?」,心想「如果能走的話,早就離開了」,這麼能輕易明白的道理,在我身上就這麼難以理解,萬事皆有因,而螢幕前的你是否能理解我呢?看著行事曆上的工作吧,「六月十九日,校定期末考週」這下明白了吧,原本以為可以託付給學弟撐著弄分散式部分,沒想到碩一期末時期這麼忙碌,弄個作業就兩三天不見人影,實驗室好幾週進入三班工作制。

撐過了幾週的工作準備和實驗環境修整,期末考週終於可以好好休息,考題總要給老師弄好,助教輕鬆地去監考就行了。期末考當天監考完,由於沒有確切的參考答案,當下也不知道怎麼向同學描述怎麼寫才是對的,要提示到哪種地步,當下感慨萬分,「對不起,這裡你要自己想,我不清楚」。

原以為老師很快就可以改好考卷,沒想到突如其來的論文 deadline,使得改考卷一事被拖延,然而送成績又是一週後的事情,先放個三天讓老師去改。催一下進度,發現一題也沒改完,先改了兩題,剩下的題目再給老師改。在放個兩天,還是沒有太多的進展,再跟老師要了兩題來改,到最後還是由我改了大部分的題目,為 … 為什麼會變成那樣?

「為 ... 為什麼會變成那樣」-《情色漫畫老師》

七月初到,仍然沒有辦法離開學校,事情接踵而來,弄完轉系考才能離開,又有實驗室經費要花,交代事情的當下只有我在學校,「嗯?怎麼?」對於研究生要在一早十點九點到實驗室,想必是個相當難的議題,學長們可是曾經全員不在而被叫上去罵呢,而我嘗試支持了一年多,電話從我座位旁響起到接起已成為最佳化的結果。在空無一人的早晨接電話,對於指定任務交代給尚未清醒的學弟等。買伺服器時,得再三催廠商寄送發票;買耗材時,得催學弟別忘記。

「太奇怪了」-《愛麗絲與藏六》

終於到辦公室跟老師提了兵單,才從老師口中說出「下週會簽離校,順便回去實驗室跟他們說」一回到實驗室說,便聽到「為什麼老師不願意簽我離校啦」,說出「下週可以簽離校」,感覺同學得知這消息倍感高興。而在那週開會的結束時,跟老師報告做的事情時,僅剩下我一人了,順帶把離校同意書一起簽。

回到實驗室,滿是「可以離校了」「什麼時候清東西」的議題,這些話題平時離我太遠,使得我無法參與討論。學弟反過來問「那你什麼時候打算簽?」說起這個傷心事,原來我總是比較特別的部分對吧!我不知道要提些什麼,悄敲地回應「為什麼覺得我沒簽呢?」然而,在簽之前,比我晚口試的古學長早在前幾天拿到畢業證書,而我才剛拿到手。不經開始懷疑自己的能力與價值。要從口中說出「拿到了」,內心可說是五味雜陳地說不出啊。

「我拿到了」-《情色漫畫老師》

突襲再訪

敬請期待

再續故事

敬請期待

可能走向

敬請期待

誌謝

以下收錄於論文中

能順利地完成這篇論文,首先,感謝劉邦鋒和吳真貞老師的指導,在論文架構和描
述手法的教導,才使得篇幅雜亂的初稿便得更加地易於理解,討論過程中更加地精
練專業知識,學生在此衷心感謝老師。

特別感謝中央大學的郭人維學長,拉拔在演算法及資料結構領域上的研究,其給予
的助力使得論文開花結果。更感謝在網路上許許多多來自各方的朋友分享研究心得
,讓彼此切磋茁壯。

在進入臺灣大學研究所的這兩年中,感謝實驗室學長們的鼓勵與支持,本對於學術
研究文化和自身能力的迷茫,接受學長們的啟示後,最終得以撐過第一學年。在第
二年中,感謝共同奮戰論文的古耕竹、古君葳、鄭以琳、吳軒衡等同學,彼此加油
打氣,使得在撰寫論文的路上並不孤單,督促進展、協助撰寫與驗證想法更加地順
利,願你們也能順利畢業、研究出滿意的成果。

在研究實驗上,感謝實驗室學弟張逸寧、林明璟、蔡慶源、朱清福的參與,被迫實
作出放置於批改娘系統上題目,這些題目原本為論文的一小部分,可透過不同資料
結構與算法解決,在本篇追求效能極致的路上貢獻了一份心力,為本實驗結果給予
更有信心的立論基礎。願你們在接下來的一年裡,經過老師指導與同學們相互引領
下順利畢業。

此外,特別感謝高中時期帶入門的溫健順老師,在選擇領域分組時,相信我在資訊
領域上的發展,拉近資訊組培養,經歷三年的教導後,才能順利走向這一條道路。

最後,感謝家人們一路相伴,進入資訊工程領域後,經歷大學轉學、延畢到研究所
的路上,對我的選擇給予支持。

感謝上述的各位與師長們一路上的支持與資助。

Read More +