解題區►解題區 - UVa

UVa 12404 - Trapezium Drawing

Problem

給予梯形兩點座標、四個邊長。找到另外兩點座標。

Sample Input

1
2
1
0 0 20 0 10 14 8

Sample Output

1
2
Case 1:
14.00000000 8.00000000 0.00000000 8.00000000

Solution

向量旋轉找解。

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
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-6
#define MAXN 131072
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);
    }
    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;
	} 
};
double dist(Pt a, Pt b) {
	return hypot(a.x - b.x, a.y - b.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;
}
Pt rotateRadian(Pt a, double radian) {
	double x, y;
	x = a.x * cos(radian) - a.y * sin(radian);
	y = a.x * sin(radian) + a.y * cos(radian);
	return Pt(x, y);
}
double solve(double a, double b, double c, double d) {
	// d^2 - x^2 = b^2 - (a - x - c)^2
	// d^2 - x^2 = b^2 - (a-c - x)^2
	// d^2 - x^2 = b^2 - ((a-c)^2 - 2(a-c)x + x^2)
	// d^2 - x^2 = b^2 - (a-c)^2 + 2(a-c)x - x^2
	// d^2 - b^2 + (a-c)^2 = 2(a-c)x
	double x;
	x = (pow(d, 2) - pow(b, 2) + pow(a-c, 2))/(2 * (a-c));
	return x;
}
int main() {
	int testcase, cases = 0;
	double x, y;
	scanf("%d", &testcase);
	while (testcase--) {
		Pt A, B, C, D;
		double a, b, c, d;
		scanf("%lf %lf", &x, &y);
		A = Pt(x, y);
		scanf("%lf %lf", &x, &y);
		B = Pt(x, y);
		scanf("%lf %lf %lf", &b, &c, &d);
		a = dist(A, B);
		x = solve(a, b, c, d);
		
		Pt vAB = (B - A) / a;
		double theta = atan2(sqrt(d*d - x*x), x);
		D = rotateRadian(vAB, theta) * d + A;
		C = D + vAB * c;
		printf("Case %d:\n", ++cases);
		printf("%.8lf %.8lf %.8lf %.8lf\n", C.x, C.y, D.x, D.y);
	}
	return 0;
}
/*
1
0 0 20 0 10 14 8
8
0 0 20 0 10 14 8
0 0 20 0 8 14 10
20 0 0 0 10 14 8
20 0 0 0 8 14 10
8 0 8 20 10 14 8
8 0 8 20 8 14 10
0 20 0 0 10 14 8
0 20 0 0 8 14 10
*/
Read More +
解題區►解題區 - UVa

UVa 10397 - Connect the Campus

Problem

在現有的鋪設下，還有幾處建築物之間沒有連通。

找到花費最小的歐基里德距離生成樹

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
4
103 104
104 100
104 103
100 100
1
4 2
4
103 104
104 100
104 103
100 100
1
4 2

Sample Output

1
2
4.41
4.41

Solution

直接用 kruskal 就可以完成，但是建造邊最慘將會達到 O(n^2)，因此效率並不好，好幾年之後回過頭來寫這一題。

對於 EMST 可以使用 Delaunay triangulation 完成。Delaunay triangulation 原則上可以在 O(n log n) 時間內完成。由於 EMST 是 Delaunay 的 subgraph，而 Delaunay 保證 edge 數最多為 3n - 6。套用 kruskal 的 O(E log E) 算法就能保證在 O(n log n) 時間內完成。

Delaunay triangulation 目前實作有 D&C 和 random 兩種。

計算幾何資料請參照 morris821028/Computational-Geometry 下載。

廣泛的比較下，兩者期望都在 O(n log n) 完成，而實際結果 D&C 普遍速度快很多。random 作法很吃機率期望，原因是要支持動態的 point location 操作，沒有一個好的資料結構來保證每一步的搜索效率，教科書上給予一個類似可持久化結構的 DG structure，深度是期望的 O(log n)，實作起來只會比 O(n) 快個常數倍。但 random increase algorithm 對於演算法的證明的確是比較容易，而且步驟相當好說明。

當效率不好去學 D&C algorithm，一開始要對座標進行排序，也就是不支持動態 (離線操作)，接著針對 x 座標剖半，兩個完成 Delaunay triangulation 的凸包進行合併，接著需要將中間縫隙穿針引線地縫起來。因此要找到兩個凸包的下公切線，然後開始攀爬上去，保證一開始的下公切線一定是 Delaunay edge，然後開始窮舉下一個 Delaunay edge，過程中也不斷地移除不適的邊。

有相當不錯的資料結構可以快速地搜索公切線、圍繞凸包的頂點 … 等，但是根據教科書給予的計算，每一個點的 degree 期望值不超過 9，意即偷偷地窮舉攀爬不影響效率。

關於三點共圓，詢問一點是否在圓內的操作，投影到拋物面上，三點在投影結果上拉出一個平面，若點在圓內，則保證該點在平面的下方。求出外心計算，會造成誤差 (無法儲存除法運算結果)，換成拋物面的思路魯棒性高。

下附 D&C algorithm 的做法，關於 random 就放在 github repo 封存了。

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
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <assert.h>
#include <string.h>
#include <list>
using namespace std;
#define eps 1e-8
#define MAXN (1048576)
#define MAXV 1024
struct Point {
    double x, y;
    int id;
    Point(double a = 0, double b = 0, int c = -1):
    	x(a), y(b), id(c) {}	
	Point operator-(const Point &a) const {
        return Point(x - a.x, y - a.y);
    }
    Point operator+(const Point &a) const {
        return Point(x + a.x, y + a.y);
    }
    Point operator*(const double a) const {
        return Point(x * a, y * a);
    }
	Point operator/(const double a) const {
        return Point(x / a, y / a);
    }
    bool operator<(const Point &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 Point &a) const {
		return fabs(x - a.x) < eps && fabs(y - a.y) < eps;
	}
	bool operator!=(const Point &a) const {
		return !(fabs(x - a.x) < eps && fabs(y - a.y) < eps);
	} 
	void read(int id = -1) {
		this->id = id;
	}
	double dist(Point b) {
		return hypot(x - b.x, y - b.y);
	}
	double dist2(Point b) {
		return (x - b.x) * (x - b.x) + (y - b.y) * (y - b.y);
	}
	void print() {
		printf("point (%lf, %lf)\n", x, y);
	}
};
struct Point3D {
	double x, y, z;
	Point3D(double a = 0, double b = 0, double c = 0):
		x(a), y(b), z(c) {}
	Point3D(Point p) {
		x = p.x, y = p.y, z = p.x * p.x + p.y * p.y;
	}
	Point3D operator-(const Point3D &a) const {
        return Point3D(x - a.x, y - a.y, z - a.z);
    }
    double dot(Point3D a) {
    	return x * a.x + y * a.y + z * a.z;
    }
};
struct Edge {
	int id;
	list<Edge>::iterator twin;
	Edge(int id = 0) {
		this->id = id;
	}
};
int cmpZero(double v) {
	if (fabs(v) > eps)	return v > 0 ? 1 : -1;
	return 0;
}
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);
}
Point3D cross(Point3D a, Point3D b) { // normal vector
    return Point3D(a.y * b.z - a.z * b.y 
				 , -a.x * b.z + a.z * b.x
				 , a.x * b.y - a.y * b.x);
}
int inCircle(Point a, Point b, Point c, Point p) {
	if (cross(a, b, c) < 0)
		swap(b, c);
	Point3D a3(a), b3(b), c3(c), p3(p);
//	printf("%lf %lf %lf\n", a3.x, a3.y, a3.z);
//	printf("%lf %lf %lf\n", b3.x, b3.y, b3.z);
//	printf("%lf %lf %lf\n", c3.x, c3.y, c3.z);
//	printf("%lf %lf %lf\n", p3.x, p3.y, p3.z);
	b3 = b3 - a3, c3 = c3 - a3, p3 = p3 - a3;
	Point3D f = cross(b3, c3); // normal vector
	return cmpZero(p3.dot(f)); // check same direction, in: < 0, on: = 0, out: > 0
}
int intersection(Point a, Point b, Point c, Point d) { // seg(a, b) and seg(c, d)
	return cmpZero(cross(a, c, b)) * cmpZero(cross(a, b, d)) > 0 
		&& cmpZero(cross(c, a, d)) * cmpZero(cross(c, d, b)) > 0;
}
class Delaunay {
	public:
	list<Edge> head[MAXV]; // graph
	Point p[MAXV];
	int n, rename[MAXV];
	void init(int n, Point p[]) {
		for (int i = 0; i < n; i++)
			head[i].clear();
		for (int i = 0; i < n; i++)
			this->p[i] = p[i];
		sort(this->p, this->p + n);
		for (int i = 0; i < n; i++)
			rename[p[i].id] = i;
		this->n = n;
		divide(0, n - 1);
	}
	void addEdge(int u, int v) {
		head[u].push_front(Edge(v));
		head[v].push_front(Edge(u));
		head[u].begin()->twin = head[v].begin();
		head[v].begin()->twin = head[u].begin();
	}
	void divide(int l, int r) {
		if (r - l <= 2) { // #point <= 3
			for (int i = l; i <= r; i++)
				for (int j = i+1; j <= r; j++)
					addEdge(i, j); 
			return;
		}
		int mid = (l + r) /2;
		divide(l, mid);
		divide(mid + 1, r);
		
		list<Edge>::iterator it;
		int nowl = l, nowr = r;
		
//		printf("divide %d %d\n", l, r);
		for (int update = 1; update; ) { // find left and right convex, lower common tangent
			update = 0;
			Point ptL = p[nowl], ptR = p[nowr];
			for (it = head[nowl].begin(); it != head[nowl].end(); it++) {
				Point t = p[it->id];
				double v = cross(ptR, ptL, t);
				if (cmpZero(v) > 0 || (cmpZero(v) == 0 && ptR.dist2(t) < ptR.dist2(ptL))) {
					nowl = it->id, update = 1;
					break;
				}
			}
			if (update)	continue;
			for (it = head[nowr].begin(); it != head[nowr].end(); it++) {
				Point t = p[it->id];
				double v = cross(ptL, ptR, t);
				if (cmpZero(v) < 0 || (cmpZero(v) == 0 && ptL.dist2(t) < ptL.dist2(ptR))) {
					nowr = it->id, update = 1;
					break;
				}
			}
		}
		
		addEdge(nowl, nowr); // add tangent
//		printf("add base %d %d\n", nowl, nowr);
		for (int update = 1; true;) {
			update = 0;
			Point ptL = p[nowl], ptR = p[nowr];
			int ch = -1, side = 0;
			for (it = head[nowl].begin(); it != head[nowl].end(); it++) {
//				ptL.print(), ptR.print(), p[it->id].print();
				if (cmpZero(cross(ptL, ptR, p[it->id])) > 0
					&& (ch == -1 || inCircle(ptL, ptR, p[ch], p[it->id]) < 0))
					ch = it->id, side = -1;
//				printf("test L %d %d %d\n", nowl, it->id, inCircle(ptL, ptR, p[ch], p[it->id]));
			}
			for (it = head[nowr].begin(); it != head[nowr].end(); it++) {
				if (cmpZero(cross(ptR, p[it->id], ptL)) > 0
					&& (ch == -1 || inCircle(ptL, ptR, p[ch], p[it->id]) < 0))
					ch = it->id, side = 1;
//				printf("test R %d %d %d\n", nowr, it->id, inCircle(ptL, ptR, p[ch], p[it->id])); 
			}
			if (ch == -1)	break; // upper common tangent
//			printf("choose %d %d\n", ch, side);
			if (side == -1) {
				for (it = head[nowl].begin(); it != head[nowl].end(); ) {
					if (intersection(ptL, p[it->id], ptR, p[ch])) {
						head[it->id].erase(it->twin);
						head[nowl].erase(it++);
					} else
						it++;
				}
				nowl = ch;
				addEdge(nowl, nowr);
			} else {
				for (it = head[nowr].begin(); it != head[nowr].end(); ) {
					if (intersection(ptR, p[it->id], ptL, p[ch])) {
						head[it->id].erase(it->twin);
						head[nowr].erase(it++);
					} else
						it++;
				}
				nowr = ch;
				addEdge(nowl, nowr);
			}
		}
	}
	
	vector< pair<int, int> > getEdge() {
		vector< pair<int, int> > ret;
		list<Edge>::iterator it;
		for (int i = 0; i < n; i++) {
			for (it = head[i].begin(); it != head[i].end(); it++) {
				if (it->id < i)
					continue;
//				printf("DG %d %d\n", i, it->id);
				ret.push_back(make_pair(p[i].id, p[it->id].id));
			}
		}
		return ret;
	}
} tool;
struct edge {
	int x, y, v;
	edge(int a = 0, int b = 0, int c = 0):
		x(a), y(b), v(c) {}
	bool operator<(const edge &a) const {
		return v < a.v;
	}
};
int parent[1024], weight[1024];
void init(int n) {
    for(int i= 0; i <= n; i++)
        parent[i] = i, weight[i] = 1;
}
int findp(int x) {
    return x == parent[x] ? x : (parent[x]=findp(parent[x]));
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if (x == y)	return 0;
    if(weight[x] > weight[y])
        weight[x] += weight[y], parent[y] = x;
    else
        weight[y] += weight[x], parent[x] = y;
    return 1;
}
int main() {
	int n, m, cases = 0;
	Point p[MAXV];
	while (scanf("%d", &n) == 1) {
		init(n);
		int x, y;
		int e = 0;
		for (int i = 0; i < n; i++) {
			scanf("%d %d", &x, &y);
			p[i] = Point(x, y, i);
		}
		
		tool.init(n, p);
			
		vector<edge> E;
		vector< pair<int, int> > DG = tool.getEdge();
		for (int i = 0; i < DG.size(); i++) {
			x = DG[i].first, y = DG[i].second;
			int v = (p[x].x - p[y].x) * (p[x].x - p[y].x) + 
						(p[x].y - p[y].y) * (p[x].y - p[y].y);
			E.push_back(edge(x, y, v));
//			printf("DG %d %d %d\n", x, y, v);
		}
		
		scanf("%d", &m);
		for (int i = 0; i < m; i++) {
			scanf("%d %d", &x, &y);
			x--, y--;
			e += joint(x, y);
		}
		
		sort(E.begin(), E.end());
		double ret = 0;
		for (int i = 0; i < E.size(); i++) {
			x = E[i].x, y = E[i].y;
			if (joint(x, y)) {
				ret += sqrt(E[i].v);
				e++;
				if (e == n - 1)
					break;
			}
		}
		printf("%.2lf\n", ret);
	}
	return 0;
}
/*
2
1 1
2 2
0
1
1 1
0
4
103 104
104 100
104 103
100 100
1
4 2
4
3 4
4 0
4 3
0 0
1
4 2
*/
Read More +
學校課程►通識課程

[通識] 文明的進程 小組報告

主題

跨國的文明競逐與衝突－原住民的文化問題

報告核心－文明的傲慢

「原住民」稱呼為何而來？

誠心臣服在我太陽帝國之下

正因為我們是侵略者！他們才是 真‧台灣人 。

AcFun 線上看－《賽德克巴萊》

在評論中大陸人這麼說

  • 「為什麼他們不說國語？」
  • 「一隻豬發生的血案？」
  • 「他們才是真台灣人啊。」

都已經被我們給文明化了

要求弱勢族群做出相同的行為－那就是一種 傲慢 。

文化差異

漢人文化需要競爭，做任何事情都需要競爭，而原住民只要在工作上能夠溫飽就能快樂過活，藉由唱歌舞蹈等表現方式來闡述他們的快樂，及時行樂整是他們的天性，說他們懶惰不上進才是我們的傲慢。相較於競爭，他們是互助合作的生命共同體，在那種生存環境下，農耕、狩獵都要互相幫忙，你說競爭下的快樂帶給多少回饋？

把我的尊嚴還給我！

如何表現自己的英勇事蹟？奮勇殺敵、狩獵得到的 骸骨 作為一個能力階層。即使如此，敬老尊賢是重要的文化，年齡階層而非能力階層。做為一個活在漢人社會的人而言，能力若決定一生，而談快樂？雖然能力不如人，難道就培養不出比自己厲害的人？也許虎媽就是這麼來的。

還敢帶刀 ... 混蛋！

佩刀難道錯了嗎？佩刀是因為生活所需，也是我們地位的象徵。憑什麼要求不能帶刀，那你們帶刀又是什麼意思，相比中古世紀騎士可以制裁的對象，低層社會人們只能對自己以下的對象進行攻擊。

融入現代社會

  • 第一階段－原住民成年人
    從成年人開始步入社會，雖然一開始會接受很殘酷的生活適應，還必須使用 漢姓 ，論名字對自尊的重要性，即使謀求到工作，並且逐漸適應生活所需。(有多少人能失去自己的名字？)
  • 第二階段－孩子教育
    由於長時間活在漢人社會，孩子學習也就必須上小學，然而文化的成長背景不同下，做為父母能教導什麼給孩子？就因為環境不同，知識理解的差異所引來歧視，難道就是錯的嗎？
  • 第三階段－傳統繼承
    村落沒有新血、沒有傳承，不就是鼓勵他們進入漢人社會的原因嗎？

什麼樣背景的人用什麼方式學，不是比較好理解嗎？學習成績不好沒什麼好擔心，只是規格面向不同。不懂不是問題，只是要換的方式。

保有精神

也改變不了這張不被文明認同的臉

我們的信仰、精神，藉由血緣牽連在一起。

巴萬，你的獵場在哪裡？

矛盾所在

  • 用很多補償條款鼓勵原住民進入我們漢人社會，但又希望他們保有他們自己的文化？

鼓勵改變，但卻又希望不變？(你們這群人到底想怎樣！)

  • 武力較強的文明使得我們成功掠奪這塊土地，而這種文明真的是文明嗎？難道不就是個野蠻人？
  • 想想印地安原住民的文化，真的是所謂低於來自被歐洲驅逐的人們所擁有的嗎？
  • 如果你們所說小七是文明的象徵？想要成為你們所說的文明文化有錯嗎？

反問小朋友：「沒有漢堡和薯條，你們都吃什麼？」小朋友答說，就吃海裡抓的九孔和龍蝦。

  • 文章中見到蘭嶼小孩吃山珍海味，那豈不是反了？依照生活的飲食水準，到底是誰過得奢侈？

世界原住民

當年英國統治的殖民地眾多，要不是他們可以退回祖國，那群人也是相當龐大的原住民。然而我們仗著人數眾多，無法退出的處境，厚臉皮地活在這片土地。不是中國對待少數民族的方式，他們在同一個文化脈絡下分支成長，即使不能理解，也能知道自己是同一脈人，已經磨得相當長久的時間。

縱使看著別國對待本國原住民的方式，例如：規劃保護區、歸還土地… 等，同時也表明了曾經使用過的暴力，他們的處境與我們台灣不同，他們有原本的家可以回，而我們必須對抗其他國家的勢力，必須與原住民站在同一條船上，也許對待他們的方式相比別國來說殘酷，一旦我們的立場被別國 (如中國，他們又會怎麼對待原住民？) 取代，那到底是誰殘酷？

被消費的文化

文明化造就觀光行為

觀光是大多數人的娛樂，也因此造就服務業的產生。談談服務業與文明化的關係

這個新的公民身分的尊貴性，首先意味著華人社會本來以長幼輩分及遠近
親疏為基礎的傳統人際關係階序必須被鬆動，好讓尊貴的自豪自信得以越過這
些差異位置所包含的舉止規範和情感限制，而成為所有主體都可以近用的現代
情感特質。在這方面，第一個重要的結構性發展就是台灣產業結構劇變後的服
務業人際互動模式，以及隨之在日常生活中不斷重複的互動消費實踐，它們都
使得新規訓不再只是外加的強制和要求，而得以徹底融入主體的生活活動與內
在自我情感。

這深入探討可能要問一下何春蕤老師，總之身處服務業的情感，肯定是原住民們所無法理解的，一開始覺得他們好客，不知不覺地商業化他們，直到他們的好心被利用，才逐漸地被厭惡。

反思

當我們對外說出「我們台灣人」到底是指那些人？是活在這片土地上的所有人？那接下來的話就是共同意識嗎？正因為要對外證明我們是個國，才急切地想要讓所有活在這片土地上的人，至少有一個共同意志？

我們用更殘酷的方式生存，剝奪那些活在幕後的人的生存條件與資源，真的有比原住民文明嗎？追求文明結果，竟是雙面刃？

探討

在各國文化的核心目標不同時，它們對待原住民的方式也有所不同，到底是給予相同地位？還是給予空間適性發展？我想這牽涉到－到底有沒有必要活在「社會」牢籠，他們明明不用看處在強勢文化人們的臉色，自給自足活得很好，為何他們要踏入我們的文化？

也許以前原住民的人數與文化有關係，為了生存不得不離開原本的文化，背負著必須學習更多文化知識的壓力。這種不對稱的學習，真的造就我們欺壓原住民了嗎？

文化模式與人口承載量

造成必要的出走的主因。根據人口普查統計，至今原住民已經從日治時代的七萬多人暴增到五十多萬人，它們的生活習性支撐這麼多人嗎？

看待偏見

偏見有時也是一種讚美 。即使是你所認為不文明的舉動，不就是正因為做了你做不到的事情？

文化分工

唱歌、表演真的是唯一生存之道？原住民未來若要發展特色，難道唱歌表演就是唯一了嗎？在很多原住民歌手的興起下，就只能朝著同一個方向嗎？

學校教育

窮鄉僻壤的村落，書上這麼多內容壓根沒見過，為何而學？遵守什麼規矩？

補償條例

一個跨世代的心態，但要知道強勢文化下也有弱勢成員，而生存的價值是因為他們的需求而存在，有時給予環境正表示處於文明的鑑賞期。

生活教育

生活就是最好的教育，有人走得出去，也一定會有人走不出去，為了 部落 而走的民族精神？

器具演進

從人工到電動－難道有人畫畫一開始就學電繪嗎？沒什麼大驚小怪的，會電腦打字就不會寫字了嗎？

Read More +
解題區►解題區 - UVa

UVa 1674 - Lightning Energy Report

Problem

給一棵樹，接著有數次操作將路徑 (u, v) 上的所有節點權重加上 k。

請問最後每一個點帶有的權重為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1 
9 
0 1
1 2
2 3
2 4
2 7
7 8
7 6
6 5
5 
1 4 10 
3 5 3 
0 8 5 
1 6 10 
4 4 100

Sample Output

1
2
3
4
5
6
7
8
9
10
Case #1: 
5 
25 
28 
3 
110 
3 
13 
18 
5

Solution

參照 zerojudge b322. 樹形鎖頭 的解法。

解說圖

A[] : 子樹總和
B[] : 節點權重

增加路徑 u 到 v 的權重為 k 時，路徑相當於 u 到某點 x 再到 LCA(u, v) 接著 y 最後 v。

那我們增加節點 u, v 的權重 B[u] += k, B[v] += k，減少其 LCA 的權重 B[LCA(u, v)] -= 2k，然後你會觀察 A[] 的部分，權重增加 k 的只會有 u-v 之間的所有節點。

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
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
#define MAXV 65536
int visited[MAXV];
vector<int> tree[MAXV];
int parent[MAXV], weight[MAXV];
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(x == y)
        return 0;
    if(weight[x] > weight[y])
        weight[x] += weight[y], parent[y] = x;
    else
        weight[y] += weight[x], parent[x] = y;
    return 1;
}
// LCA
vector< pair<int, int> > Q[MAXV];// query pair, input index - node
int LCA[131072]; // [query time] input query answer buffer.
void tarjan(int u, int p) {// rooted-tree.
    parent[u] = u;
    for(int i = 0; i < tree[u].size(); i++) {//son node.
        int v = tree[u][i];
        if(v == p)	continue;
        tarjan(v, u);
        parent[findp(v)] = u;
    }
    visited[u] = 1;
    for(int i = 0; i < Q[u].size(); i++) {
        if(visited[Q[u][i].second]) {
            LCA[Q[u][i].first] = findp(Q[u][i].second);
        }
    }
}
int dfs(int u, int p, int weight[]) {
    int sum = weight[u];
    for(int i = 0; i < tree[u].size(); i++) {//son node.
        int v = tree[u][i];
        if(v == p)	continue;
        sum += dfs(v, u, weight);
    }
    return weight[u] = sum;
}
int main() {
    //	freopen("in.txt", "r+t", stdin);
    //	freopen("out2.txt", "w+t", stdout);
    int n, m, x, y;
    int testcase, cases = 0;
    int X[MAXV], Y[MAXV], K[MAXV];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            tree[i].clear();
        for (int i = 1; i < n; i++) {
            scanf("%d %d", &x, &y);
            tree[x].push_back(y);
            tree[y].push_back(x);
        }
        
        int weight[MAXV] = {}, extra[MAXV] = {};
        for (int i = 0; i < n; i++)
            visited[i] = 0, Q[i].clear();
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &X[i], &Y[i], &K[i]);
            Q[X[i]].push_back(make_pair(i, Y[i]));
            Q[Y[i]].push_back(make_pair(i, X[i]));
        }
        tarjan(0, -1);
        for (int i = 0; i < m; i++) {
            extra[LCA[i]] += K[i];
            weight[X[i]] += K[i];
            weight[Y[i]] += K[i];
            weight[LCA[i]] -= 2 * K[i];
        }
        dfs(0, -1, weight);
        
        printf("Case #%d:\n", ++cases);
        for (int i = 0; i < n; i++)
            printf("%d\n", weight[i] + extra[i]);
    }
    return 0;
}
Read More +
解題區►解題區 - UVa

UVa 1659 - Help Little Laura

Problem

平面上有 N 個點，並且給定數條有向邊，在這個遊戲中，必須從某個點出發，沿著邊回到起點。每一條邊最多經過一次，而點可以重複走。

每經過一條邊，可以獲益每單位長 X 的利益，但是使用一條邊的成本為 Y。

請問最大獲益為何？

Sample Input

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

Sample Output

1
2
3
Case 1: 16.00 
Case 2: 0.00 
Case 3: 522.18

Solution

目標將每一個點調整 indeg = outdeg，要將多餘的邊捨去，只要滿足 indeg = outdeg，則可以表示平面上有數個尤拉環道。

接著建造最少費用流的模型，來捨去掉多餘的邊。當存有邊 e(i->j) 時，outdeg[i]++, indeg[j]++，一開始選擇所有 cost(e(i->j)) > 0 的邊，作為初始盤面，對於 cost(e(i->j)) < 0 先不選，選擇獲益為負的結果並不好。

如果 cost(e(i->j)) > 0，建造邊 i->j, flow: 1, cost: cost(e(i->j))，假使在最少費用流中選擇這一條邊時，就會將 deg 數量減少。對於 cost(e(i->j)) < 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
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <queue>
#include <functional>
#include <deque>
#include <algorithm>
using namespace std;
#define eps 1e-8
struct Node {
    int x, y, cap;
	double cost;// x->y, v
    int next;
} edge[1000005];
int e, head[600], prev[600], record[600], inq[600];
double dis[600];
void addEdge(int x, int y, int cap, double cost) {
    edge[e].x = x, edge[e].y = y, edge[e].cap = cap, edge[e].cost = cost;
    edge[e].next = head[x], head[x] = e++;
    edge[e].x = y, edge[e].y = x, edge[e].cap = 0, edge[e].cost = -cost;
    edge[e].next = head[y], head[y] = e++;
}
double mincost(int s, int t, int n) {
    double mncost = 0;
	int flow, totflow = 0;
    int i, x, y;
    double oo = 1e+30;
    while(1) {
    	for (int i = 0; i <= n; i++)
    		dis[i] = oo;
        dis[s] = 0;
        deque<int> Q;
        Q.push_front(s);
        while(!Q.empty()) {
            x = Q.front(), Q.pop_front();
            inq[x] = 0;
            for(i = head[x]; i != -1; i = edge[i].next) {
                y = edge[i].y;
                if(edge[i].cap > 0 && dis[y] > dis[x] + edge[i].cost) {
                    dis[y] = dis[x] + edge[i].cost;
                    prev[y] = x, record[y] = i;
                    if(inq[y] == 0) {
                        inq[y] = 1;
                        if(Q.size() && dis[Q.front()] > dis[y])
                            Q.push_front(y);
                        else
                            Q.push_back(y);
                    }
                }
            }
        }
        if(dis[t] == oo)
            break;
        flow = 0x3f3f3f3f;
        for(x = t; x != s; x = prev[x]) {
            int ri = record[x];
            flow = min(flow, edge[ri].cap);
        }
        for(x = t; x != s; x = prev[x]) {
            int ri = record[x];
            edge[ri].cap -= flow;
            edge[ri^1].cap += flow;
            edge[ri^1].cost = -edge[ri].cost;
        }
        totflow += flow;
        mncost += dis[t] * flow;
    }
    return mncost;
}
int main() {
	int cases = 0;
    int N, X, Y;
    int x[128], y[128], u;
    while (scanf("%d %d %d", &N, &X, &Y) == 3 && N) {
    	vector<int> g[128];
    	for (int i = 1; i <= N; i++) {
    		scanf("%d %d", &x[i], &y[i]);
    		while (scanf("%d", &u) == 1 && u)
    			g[i].push_back(u);
		} 
		
    	e = 0;
		memset(head, -1, sizeof(head));	
		int deg[128] = {};
		double sumCost = 0;
		for (int i = 1; i <= N; i++) {
			for (int j = 0; j < g[i].size(); j++) {
				u = g[i][j];
				double d = hypot(x[i] - x[u], y[i] - y[u]);
				double cost = d * X - Y;
				if (cost < 0) {
					addEdge(u, i, 1, -cost);
				} else {
					sumCost += cost;
					addEdge(i, u, 1, cost);
					deg[u]--, deg[i]++;
				}
			}
		}
		int source = 0, sink = N + 1;
		for (int i = 1; i <= N; i++) {
			if (deg[i] > 0)	addEdge(source, i, deg[i], 0);
			if (deg[i] < 0)	addEdge(i, sink, -deg[i], 0);
		}
		double mncost = mincost(source, sink, N+1);
		printf("Case %d: %.2lf\n", ++cases, sumCost - mncost + eps);
    }
    return 0;
}
/*
4 5 1 
0 0 2 3 0 
1 0 3 4 0 
1 1 4 0 
0 1 1 0 
1 2 1 
0 0 0 
10 7 2 
0 0 2 4 0 
5 0 3 0 
5 10 4 10 0 
2 3 5 0 
7 5 6 0 
0 11 1 0 
8 0 10 5 0 
18 3 7 0 
14 5 8 1 0 
12 9 9 0 
0
*/
Read More +
解題區►解題區 - UVa

UVa 1649 - Binomial coefficients

Problem

組合的反函數，現在給定組合數，輸出是由哪幾種組合可以配出組合數。

Sample Input

1
2
3
2
2
15

Sample Output

1
2
3
4
1
(2,1)
4
(6,2) (6,4) (15,1) (15,14)

Solution

先預見表，完成前幾項的結果。

看著巴斯卡三角形單純看 i，對於 C(n, i) 是一個嚴格遞增的函數。因此窮舉 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
#include <stdio.h>
#include <map> 
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 1024
const long long MAXVAL = 1e+16, MAXVAL2 = 1e+15;
long long C[MAXN][MAXN] = {};
map<long long, vector< pair<long long, long long> > > R;
int testCombination(long long n, long long m, long long Cnm) { // test C(n, m), m < 10
	long long ret = 1;
	m = min(m, n-m);
	for (long long i = 1; i <= m; i++) {
		if (Cnm * i / (n + 1 - i) / ret  < 1)
			return 1;
		ret = ret * (n + 1 - i) / i;
	}
	return ret == Cnm ? 0 : -1;
}
vector< pair<long long, long long> > invCombination(long long n) {
	vector< pair<long long, long long> > ret;
	ret = R[n];
	for (int i = 1; i < 10; i++) {
		long long l = 1, r = n, mid;
		while (l <= r) {
			mid = (l + r)/2;
			int f = testCombination(mid, i, n); // {-1, 0, 1}
			if (f == 0) {
				ret.push_back(make_pair(mid, i));
				ret.push_back(make_pair(mid, mid - i));
				break;
			}
			if (f < 0)
				l = mid + 1;
			else
				r = mid - 1;
		}
	}
	sort(ret.begin(), ret.end());
	ret.resize(unique(ret.begin(), ret.end()) - ret.begin());
	return ret;
}
int main() {
//	printf("%d\n", testCombination(5000, 2, 12497500));
	C[0][0] = 1;
	for (int i = 1; i < MAXN; i++) {
		C[i][0] = 1;
		for (int j = 1; j <= i; j++) {
			C[i][j] = C[i-1][j-1] + C[i-1][j];
			C[i][j] = min(C[i][j], MAXVAL);
			if (j != i && C[i][j] <= MAXVAL2)
				R[C[i][j]].push_back(make_pair(i, j));
		}
	}
//	for (int i = 0; i < 10; i++)
//		printf("%lld\n", C[MAXN-1][i]);
	int testcase;
	long long n;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%lld", &n);
		vector< pair<long long, long long> > r = invCombination(n);
		printf("%d\n", (int) r.size());
		for (int i = 0; i < r.size(); i++)
			printf("(%lld,%lld)%c", r[i].first, r[i].second, i == r.size()-1 ? '\n' : ' ');
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 1614 - Hell on the Markets

Problem

金融交易，它們希望賣出、買進交易結束後的差為零。

意即將數字分兩堆的結果相同。

Sample Input

1
2
3
4
4
1 2 3 3
4
1 2 3 4

Sample Output

1
2
3
No
Yes
1 -1 -1 1

Solution

由於保證 0 < a[i] <= i，基於這一點，可以發現到只考慮一個數字 a[1] 時，必然可以湊出 1 - a[1]，當考慮第 i 大數字時，保證前 i - 1 個數字可以湊出 1 ~ (i-1)，加上第 i 個數字必然可以湊出 1 ~ (i-1)+a[i] (1, 2, 3, ..., i-1, a[i], 1+a[i], ..., i-1+a[i])。

而事實上，可以湊出所有的 1 ~ sum[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
#include <stdio.h>
#include <algorithm>
using namespace std;
	
pair<int, int> A[100000];
int main() {
	int n;
	while (scanf("%d", &n) == 1) {
		long long sum = 0;
		int ret[100000] = {};
		for (int i = 0; i < n; i++) {
			scanf("%d", &A[i].first);
			A[i].second = i;
			sum += A[i].first;
		} 
		if (sum%2) {
			puts("No");
		} else {
			puts("Yes");
			sum /= 2;
			sort(A, A+n);
			for (int i = n-1; i >= 0; i--) {
				if (sum >= A[i].first)
					sum -= A[i].first, ret[A[i].second] = 1;
				else
					ret[A[i].second] = -1;
			}
			for (int i = 0; i < n; i++)
				printf("%d%c", ret[i], i == n-1 ? '\n' : ' ');
		}
	}
	return 0;
}
Read More +
解題區►解題區 - UVa

UVa 1169 - Robotruck

Problem

在一個二維平面中，灑落 N 個垃圾，機器人從原點 (0, 0) 依序要蒐集垃圾，機器人一次承載 W 重量的垃圾，隨時可以返回原點將垃圾放下。

請問依序收集垃圾的最少花費為何？

Sample Input

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

Sample Output

1
14

Solution

一開始得到方程式 dp[i] = min(dp[j-1] + cost[j, i] + dist[j] + dist[i]) 必須滿足 w[j, i] <= C，其中 j <= i。

其中 dp[i] 表示依序收集前 i 個垃圾的最小花費，cost[j, i] 表示走訪編號 j 到 i 垃圾位置的花費，補上原點到編號 j，並且收集完從 i 回到原點。

這樣的方程式轉換需要 N^2 時間，化簡一下式子

1
2
3
dp[i] = dp[j-1] + cost[j, i] + dist[j] + dist[i]
dp[i] = dp[j-1] + cost[i] - cost[j] + dist[j] + dist[i]
dp[i] = (dp[j-1] - cost[j] + dist[j]) + cost[i] + dist[i]

會發現 i, j 獨立，也滿足垃圾重量累計遞增，因此盡可能保留 dp[j-1] - cost[j] + dist[j] 小的結果，並且重量不超過限制，當重量超過限制時，該組答案在隨後保證再也不會用到，直接捨棄之。

核心就是單調隊列的思路。

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
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <algorithm>
using namespace std;
#define MAXN 131072
int x[MAXN], y[MAXN], w[MAXN];
int cost[MAXN], dist[MAXN];
int dp[MAXN];
int f(int j) {
	return dp[j-1] - cost[j] + dist[j];
}
int main() {
	int testcase, C, N;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d", &C, &N);
		w[0] = 0, cost[0] = 0;
		for (int i = 1; i <= N; i++) {
			scanf("%d %d %d", &x[i], &y[i], &w[i]);
			cost[i] = cost[i-1] + abs(x[i] - x[i-1]) + abs(y[i] - y[i-1]);
			dist[i] = abs(x[i]) + abs(y[i]);
			w[i] += w[i-1];
		}
		// dp[i] = dp[j-1] + cost[j, i] + dist[j] + dist[i]
		// dp[i] = dp[j-1] + cost[i] - cost[j] + dist[j] + dist[i]
		// dp[i] = (dp[j-1] - cost[j] + dist[j]) + cost[i] + dist[i]
		deque<int> Q;
		Q.push_back(0);
		for (int i = 1; i <= N; i++) {
			while (!Q.empty() && w[i] - w[Q.front()] > C)
				Q.pop_front();
			dp[i] = f(Q.front() + 1) + cost[i] + dist[i];
			while (!Q.empty() && f(Q.back() + 1) >= f(i + 1))
				Q.pop_back();
			Q.push_back(i);
		}
		printf("%d\n", dp[N]);
		if (testcase)	puts("");
	}
	return 0;
}
Read More +
學校課程►計算幾何

計算幾何 - HW04

Chapter 7

7.1

Prove that for any n > 3 there is a set of n point sites in the plane such that one of the cells of Vor(P) has n−1 vertices

證明一個點個數 n > 3 的 Voronoi diagram，存在一個 cell 具有 n - 1 個頂點。

7.1

如圖所示，一個點放置在圓心，剩餘的 n - 1 個放置在圓周上。則中間的 cell 必然有 n - 1 個頂點。

7.3

Show that $\Omega (nlogn)$ is a lower bound for computing Voronoi diagrams by reducing the sorting problem to the problem of computing Voronoi diagrams. You can assume that the Voronoi diagram algorithm should be able to compute for every vertex of the Voronoi diagram its incident edges in cyclic order around the vertex.

7.3

證明 Voronoi diagram 的 lower bound $\Omega (nlogn)$，藉由 reduce 到 sorting problem。

關於 reduce 證明，將一個簡單、約束較少的問題 A，藉由一個合適的轉換，變成一個困難問題 B 的 subset，已知 A 的 lower bound，則 B 的 lower bound 至少與 A 相同。

  1. 假設排序 n 個整數 $x_{1}, x_{2}, ..., x_{n}$
  2. 轉換成 $(x_{1}, 0), (x_{2}, 0), ..., (x_{n}, 0)$ 將所有點放置在 x 軸上，並且額外增加一點 $(\infty, 0)$。將 n + 1 個點找到 Voronoi diagram，對於 $(\infty, 0)$ 的 cell 而言，恰好邊都是由另外 n 個點對應的 cell 構成 cell edge (相鄰)。假設儲存邊的順序為順或逆時針，則邊的順序等價排序結果。

最後如上圖所示，又已知轉換需要 $O(n)$，sorting $\Omega (nlogn)$，則 Voronoi diagram 的 lower bound $\Omega (nlogn)$。

7.5

Give an example where the parabola defined by some site $p_{i}$ contributes more than one arc to the beach line. Can you give an example where it contributes a linear number of arcs?

7.5

如上圖所示，$p_{i}$ 拉出的拋物線 (parabola) 有可能提供多個弧 (arc)。(最左側的點提供 2 個弧)

一個點 $p_{i}$ 存有的 arc 數量與 cell($p_{i}$) 的頂點數量線性相關。由 exercose 7.1 得到最多 $O(n)$ 的頂點。同理 arc 數量最多 $O(n)$。

beach line 上的 arc 數最多為 Voronoi diagram 的 edge 數，又 Voronoi diagram 的 edge 最大數為 $3n - 6$，也因此最多為 $O(n)$

7.10

Let P be a set of n points in the plane. Give an $O(nlogn)$ time algorithm to find two points in P that are closest together. Show that your algorithm is correct.

Algorithm:

  1. 建造 Voronoi Diagram by fortune’s algorithm－$O(nlogn)$
  2. 對於每一個 cell($p_{i}$) 檢查鄰居 cell($p_{neighbor}$)，計算 $distance(p_{i}, p_{neighbor})$ 的結果。Voronoi diagram 的 edge 數 $3n - 6$，每一條 edge 檢查只需要 $O(1)$。－$O(n)$

證明：每一個點所張開的 cell 只會與相鄰的 cell 最近，否則不符合 Voronoi diagram 的定義。

7.14

Show that the farthest point Voronoi diagram on n points in the plane has at most 2n−3 (bounded or unbounded) edges. Also give an exact bound on the maximum number of vertices in the farthest point Voronoi diagram.

  • 歐拉公式：$v - e + f = 2$
  • 一個頂點至少三條邊。
  • farthest point Voronoi diagram 的最多有 n - 2 個頂點。
    • 對於每一個頂點而言，通過其相鄰 cell 對應的點的外接圓，其圓包含所有平面點。
    • 這種圓最多 n - 2 個。
  • 從隨機增量算法中得知，插入一個點時，最多增加一個 vertex (繞行時，會刪除對於 cell 相交兩個線段之間的所有 vertex，這種 vertex 至少一個，並且增加與線段的交點 1 個)。 $v(3) = 1, v(n) = v(n-1) + 1 \text{ for } n > 3$
  • 考慮增加一個虛點，連接所有 unbounded edge
    $v - e + f = 2 \Rightarrow (n-2+1) - e + n = 2 \Rightarrow e = 2n - 3$。

Chpater 9

9.2

The degree of a point in a triangulation is the number of edges incident to it. Give an example of a set of n points in the plane such that, no matter how the set is triangulated, there is always a point whose degree is n−1.

對於任意三角化的結果，總會有一個點的 degree = n - 1。

9.2

  • 此點一定能用一條線區隔所有剩餘點。
  • 剩餘 n - 1 個點，一定能滿足任兩點的連線不遮蔽其他的點。

example：n - 1 個點落在 $y = e^{x}$ 上，且 $x < p$，另外一點在 $(p, q)$

9.4

Prove that the smallest angle of any triangulation of a convex polygon whose vertices lie on a circle is the same. This implies that any completion of the Delaunay triangulation of a set of points maximizes the minimum angle.

對於所有頂點共圓的凸多邊形，任何的三角化的最小角度都會相同。

  1. 任何三角形必然是圓上三點。
  2. 任何凸邊形的邊都會是一個三角形上的邊
  3. 三角形的邊都是圓的弦，並且對應角度正比弦長大小。
  4. 凸多邊形的最小弦長是多邊上的邊，又因一定會在三角形上，任何三角化一定包含這個最小角。

9.7

Prove that all edges of DG(Pr) that are not in DG(Pr−1) are incident to pr. In other words, the new edges of DG(Pr) form a star as in Figure 9.8. Give a direct proof, without referring to algorithm DELAUNAYTRIANGULATION.

對於新增加的邊 $e$，只會與新加入的點 $p_{r}$ 相連。

  • 從 Voronoi diagram 等價 Delaunay triangulation，加入點的 cell，不會使其他兩個 cell 從沒相鄰變成相鄰。

  • 對於 $\Delta(p_{i}, p_{j}, p_{k})$ 之間加入 $p_{r}$，由於 $C(p_{i}, p_{j}, p_{k})$ 內部不存在任何點，$C'(p_{i}, p_{r})$ (兩點當直徑)，得到 $C' \subseteq C$，且 $C'$ 內部不存在任何點，確定 $\bar{p_{i} p_{r}}$ 屬於 Delaunay 上。同理 $\bar{p_{j} p_{r}}$、$\bar{p_{k} p_{r}}$。

  • 由於 $\Delta(p_{l}, p_{i}, p_{j})$ 原本是 Delaunay 上，如果 flip $\bar{p_{i} p_{j}}$，得到 $C(p_{i}, p_{r}, p_{l}) \subseteq C(p_{l}, p_{i}, p_{j})$、$C(p_{j}, p_{r}, p_{l}) \subseteq C(p_{l}, p_{i}, p_{j})$，確定 $\bar{p_{r} p_{l}}$ 屬於 Delaunay 上。

  • 也因此，對於增加的三角形進行檢查時，每次已經保證該三角形其中兩邊一定屬於 Delaunay 上，同時必然有 $p_{r}$，flip 的邊一定會接到 $p_{r}$ 上。遞迴得證。

9.11

A Euclidean minimum spanning tree (EMST) of a set P of points in the plane is a tree of minimum total edge length connecting all the points. EMST’s are interesting in applications where we want to connect sites in a planar environment by communication lines (local area networks), roads, railroads, or the like.

  1. Prove that the set of edges of a Delaunay triangulation of P contains an EMST for P.
  2. Use this result to give an O(nlogn) algorithm to compute an EMST for P.

對於歐幾里得距離的平面最小生成樹。

  1. 證明 EMST 的 edge set 被 Delaunay triangulation 的 edge set 包含。(參考 wiki)
    目標： every edge not in a Delaunay triangulation is also not in any EMST

    • 最小生成樹的性質：任何一個 cycle 上的最重邊將不會在最小生成樹中。

    • Delaunay triangulation： If there is a circle with two of the input points on its boundary which contains no other input points, the line between those two points is an edge of every Delaunay triangulation.

      對於鈍角三角形，最大邊必然不在 EMST 中，然而對於 Delaunay triangulation 性質，必須考慮他們兩點的 boundary (shared Voronoi edge) 是否存在。

      假設 p, q 之間沒有邊於 Delaunay，則對於任意通過 p, q 的圓都存在點 r 在圓內，從性質中發現 r 到 p, q 的距離一定小於 p q 之間的距離。同時在 EMST 中，p q r 三點會構成鈍角三角形，其中 p q 是最大邊，p q 之間必然沒有邊。

  2. 找到 EMST 的 $O(nlogn)$ 算法
    Algorithm:

    1. 利用 Delaunay triangulation 找到所有邊－$O(nlogn)$
    2. 最多有 3n - 6 條邊，利用 MST 中的 kruskal’s algorithm－$O(ElogE)$
    3. $E = O(3n-6) = O(n)$，得到 $O(nlogn)$ 的做法。

9.13

The Gabriel graph of a set P of points in the plane is defined as follows:
p q Two points p and q are connected by an edge of the Gabriel graph if and only if the disc with diameter pq does not contain any other point of P.

  1. Prove that DG(P) contains the Gabriel graph of P.
  2. Prove that p and q are adjacent in the Gabriel graph of P if and only if the Delaunay edge between p and q intersects its dual Voronoi edge.
  3. Give an O(nlogn) time algorithm to compute the Gabriel graph of a set of n points

Gabriel graph：任兩點之間為直徑的圓內若沒有其他點，則兩點之間有邊。

  1. 證明 subgraph 關係。
  • 根據 Theorem 9.6 (1) 任三點圓內 $C(p_{i}, p_{j}, p_{k})$沒有其他點，但是 $C(p_{i}, p_{j})$ 內部可能存有其他點 (如單純的 n = 3 的鈍角三角形)。找到 $e_{p_{i}, p_{j}} \notin Gabriel \text{ but } e_{p_{i}, p_{j}} \in Delaunay$
  • $C(p_{i}, p_{j})$ 內部沒有其他點，則兩點之間必然有 shared Voronoi edge，符合 Theorem 9.6 (2)。得到
    $\text{ if }e_{p_{i}, p_{j}} \in Gabriel \text{ , then } e_{p_{i}, p_{j}} \in Delaunay$，得證 $g(P) \subseteq DG(P)$。
  1. 如果 $\bar{pq}$ 經過多個 Voronoi edge，則 $\bar{pq}$ 上一點 x 滿足 $$\bar{xr} < \bar{xp}, \bar{xr} < \bar{xq} \\ \Rightarrow \angle rpx < \angle prx, \angle rqx < \angle xrq \text{(triangle)} \\ \text{let } \angle rpx = a, \angle prx = c, \angle rqx = b, \angle xrq = d \\ \Rightarrow a + b + c + d = 180^{\circ} \\ \Rightarrow c + d > 90^{\circ}$$

符合圓內角性質，點 r 一定在圓內，得證 $e_{p_{i}, p_{j}} \notin Gabriel$。

  1. 在 O(n logn) 時間內完成。
    Algorithm：

    1. 利用 Delaunay triangulation 找到所有邊－$O(nlogn)$

    2. 將 $e_{p{i}, p{j}} \in DG(P)$ 進行測試是否有點落在 $C(p{i}, p{j})$－$O(n)$

      只需要拿鄰居進行檢測，鄰居最多 2 個 (共邊的三角形)。

9.14

The relative neighborhood graph of a set P of points in the plane is defined as follows: Two points p and q are connected by an edge of the relative neighborhood graph if and only if

$$d(p, q) \leq \underset{r \in P, r \neq p, q }{min} max(d(p, r), d(q, r)).$$
  1. Given two points p and q, let lune(p,q) be the moon-shaped region p q lune(p,q) formed as the intersection of the two circles around p and q whose radius is d(p,q). Prove that p and q are connected in the relative neighborhood graph if and only if lune(p,q) does not contain any point of P in its interior.
  2. Prove that DG(P) contains the relative neighborhood graph of P.
  3. Design an algorithm to compute the relative neighborhood graph of a given point set.

整體而言類似 9.13。

  1. 若 p, q 之間沒有邊，則
    $$\exists r : d(p, q) > \underset{r \in P, r \neq p, q }{min} max(d(p, r), d(q, r)) \\ \exists r : d(p, q) > d(p, r) \text{ and } d(p, q) > d(q, r)$$
    AND 就是做交集操作，不知道該怎麼寫才好。
  2. 與 9.14 依樣畫葫蘆，只是 $lune(p, q) \subseteq C(p, q)$，則更暗示 $\text{ if }e_{p_{i}, p_{j}} \in G \text{ , then } e_{p_{i}, p_{j}} \in Gabriel$
  3. 速度是 $O(n^{2})$，沒辦法單純看鄰居進行檢查。拿每一條邊進行 O(n) 窮舉。不過在分散式計算，整體是 O(n)。
Read More +
學校課程►通識課程

[通識] 文明的進程 Week 10

重大體悟

羞恥重要的性質是在行為舉止後對於 自我優越感下降 的 恐懼 ，個人害怕喪失他人的尊重，思考這些帶來的可能性，也就是羞恥情感！其實活得身分低下、與那些自認不同的人處於相同地位。

學了半學期羞恥，這時才發現那吞噬信心的巨獸－ 羞恥 ，不知道何時開始，它就像常駐技能似的，不管睡著還醒著都沒有關閉的跡象，這樣活著像遊戲 BUG 似的存在，那麼地與眾不同。

也許，早在那年發現自我弱點時，就烙上那 奴隸的印記 ，不斷地想要遮掩身分的不同，隨時隨地都要小心祕密被發現，想到個人價值有可能在一夕崩落，羞恥感壟罩整個心頭。其實我就是那身分低下的奴，不斷地遮掩印記，卻試圖想要往那更高層爬去。

既然都爬到這，還不想崩落、還不想被發現，至少還要在某些人中存有價值，帶著罪惡感不斷輪迴，也因此走了自己最不想走的路，但是不這麼做，自我價值就在瞬眼之間消散。

如今，崩落假想也隨之成長，直到那再也無法遮掩自己的脆弱前，假想帶來的恐懼不斷地侵蝕我。

回過頭來

段考檢討

寫點與印象答案比較不同的，總之能想到自己很多是零分面向的作答，無知就是我的本體。

  • 為何 淡定 、 hold 住 的情感為何在中世紀比較沒有呢？
    中世紀的人必須野蠻，對人的關係不是 朋友就是敵人 ，任何一點猶豫將把自己處於不利地位，為了生存，這些克制自我的情感將成為阻礙。
  • 解釋 內心世界 為何而生？
    隨著文明化，人與人之間的關係相當重要，在 人際互動 的親密下，考慮遠程利益，不斷地盤算要做出甚麼樣的決策，才能最適應未來、現在的人際網路，也因此要表現出那衝突、矛盾的思緒都會在內心世界中。
  • 對於中古世紀以及現代教育對於 兒童教育 的方針有何基礎的不同？
    中世紀的兒童教育，兒童就是小大人，什麼都必須知道、什麼都能做，因為它們要趕快成為大人。相對於近代，防止被帶壞、很多不能學、不能知道，不斷地隔離成人的內容。
  • 為什麼機場配置的「紅外線水龍頭」高科技廁所是一個文明化的象徵？
    隔離人與人之間的接觸，同時也是在衛生觀念的防病、防疫措施。隔絕彼此已經作為一個文明化的指標。

本周課程

本周圍繞的主題為社會結構與人際關係，不過說是禮儀與社會結構之間交互關係也可，作為階級區隔，人與人之間所需的禮儀也會有所不同。

曾經說到階級流動與禮儀之間的關係，在不同階級下，人的生活型態不同，面對不同的環境就需要不同的禮儀，即使是在相同時空下，對人制宜也是相當重要的！

階級競逐

作為看待一個社會階級流動，正因為流動的存在，也會形成激烈的競逐，而作為競逐的項目也會隨著年代、國情不同而有所變化，從文憑、車款、養生、 … 都能見得。在傳統社會的世襲中，階級也許不太變化，權貴般的生活到了現代，如果把自己家境多有錢拿出來凸顯階級，也許還比不上一個有品味、氣質、風度的平民百姓。

你的強大若無法帶給別人恩惠，充其量就是個異類。

不過從印度婆羅門教、種姓制度看來，用了一個宗教藉口使得人們相信此生所為將決定下個人生的階級，某些手段利益看來，相當高明呢！社會看起來肯定相當安定，各盡其職。如果沒有太離譜的表現，制度當初為了血統純正的說法，就能達到目標。

結構改變

當社會結構改變時，帶動的是許多職業的消失。當然在科技的發展下，也不少職業消失，而這些人去了哪裡？又有甚麼樣的心理狀態改變？

曾想過自己一身技能，在一個事件動盪下一文不值嗎？接著又要何去何從，找到自我價值？

細看武士階級的年代，其實那段日子在早些時間都消失，他們練就一身武藝，卻沒有在年代中獲得需要、找到工作，不管是在西方騎士、東方武士都有相同的處境，即使後來在重要人士旁進行護衛工作，但身分地位上也有所轉變，至少在禮儀上也必須相對於在戰場上那樣的狂野，轉為平靜的心態。

在中國歷史角度看來，從諸侯分權到王權獨大，武力霸權帶來的壟斷、和平，卻也造成武士們再也沒有表現的機會，何處才有戰場讓咱們逞逞威風？每天面對帝王鞠躬盡瘁，哪適合咱們？也因此不少人從國民崇拜的英勇武士落魄到連下一餐都找不到，即便現在沒了戰場，也要秉持著武士精神度日！絕不能讓別人看到自己軟弱的地方！

講到這，講到動物也有此特性，再凶猛的動物即使自己受傷處於弱勢，若展現脆弱的一面，也會受到反撲。

在西方歷史中，最有印象的是具有領土的貴族們，當商人興起，開始擁有大把大把鈔票時，農地生產不及鈔票來得有價值，金錢觀念勝過於階級，貴族們也無法守住自己的農民，最後要倚靠皇宮的保護，最後遺失自己的自由。「 雖然窮，但我們自由。 」這一詞也在某些勵志的文章中見到，金錢的重要性還是看個人操守吧。

投票是什麼？「有錢有勢的人動員沒錢沒勢的人進行大規模支持活動」－老師一語，全堂竊笑。

到了現代，仍然有許多國家存有兩極化，例如 墨西哥 貧民窟，上網搜尋的結果，還真是一線之隔，可謂「 住得近、習相遠 」老師的意思可能不是這樣，在分工體系下，人們從自給自足轉變到相互依賴，開始有了密切交易，同時也帶來緊張氣氛。

達爾文獎：「讓自己愚蠢的基因不再自由地傳播出去」，對人類的演化做出了貢獻。亦有人認為，達爾文獎是用來記錄「那些在演化過程中走得最慢的人們」。

內心世界

在現在的人情交易所中，深思熟慮、自我克制、精確調整情緒成為交易所的基礎籌碼，只要拿著這些籌碼去，多少能搏得人情網路，同時了解人情網路的拓樸關係，有助於思考站於哪個地位進行支持，可謂拓樸學的二分圖、三分圖之類的關係呢！一個人改變關係，可能標染都要更動！

我們將會變成一個縝密分析的生物，就為了站在有利的位置上，不斷地將訊息解析，否則無法立於社會中。必須知道情感用事也無法撼動這個世界，世界道理不依個人意志運作。

作為這一點，如果一個人思考的太多，針對、多角式、深入剖分的思考會不會造成反應速度的延遲？意即聰明到跟笨蛋似的。

國人特有現象，在一般常理下，自己做出脫格行為將會為自己帶來羞恥，對於別人做的，則會身感難堪，但是我們似乎更進化了？會感到憎恨。

Read More +