morris821028/gist:bd993ece62657892e2f3

## gistfile1.txt
// 20150101 - 20150225 Facebook Timeline.

［UVa］1679 - Easy Geometry 開學第一題！
在凸多邊形內部找一最大空白矩形。多邊形頂點數最多 10 萬個。
三分內嵌三分再內嵌二分，幾何算法從函數觀點下手的有趣題目。

〔UVa〕12415 - Digit Patterns
讀入一個 regex，一個主字串 s，請問有不同的 i 滿足 s 的子字串 s[j...i] 符合 regex，套用 NFA 轉換成 DFA，可惜的是壓縮後狀態數還是太多，即使通過劉汝佳給的 small gift testdata，而且裡面倒數第二筆測資輸出有誤。當初學的時候就有這個疑問，果然狀態總數的增長非常大。

所謂的動態 NFA 轉換 DFA 指得到底是什麼？又被劉汝佳坑了一題 QQQQQQQQ

〔UVa〕210 - Concurrency Simulator
作業系統排程 lock & unlock 模擬，去年某一天心血來潮寫，卻狂 WA。現在回過頭才發現對 quantum 的使用錯誤，在有限時間內，即使在有剩餘時間下，執行下一條單位操作，直到沒有剩餘時間，我卻用加法限制於 quantum 下，導致炸掉。

題目中 "When an unlock is executed, any program at the head of the blocked queue is moved to the head of the ready queue"，為什麼只有一個 blocked queue 元素彈出，雖然在效率考量上是這樣，誤看成全部彈出，怪不得會一直 WA。但這樣所有模擬都會完結？

〔全局最小割〕最小割 Stoer-Wagner 算法

http://blog.sina.com.cn/s/blog_700906660100v7vb.html
http://wenku.baidu.com/view/fdb484c3bb4cf7ec4afed08b.html

主算法框架不難，隨著迭代將點數縮減，每次在 G(V, E) 找到其中一組 s-t 最小割，不管最小割 s-t 是否為答案，將 s-t 合併成一個點得到 G'(V', E')，繼續迭代。答案要不在剛剛求出的 s-t 要不在 G' 中，s-t 即假設兩點位於不同的集合，如果求出的不是最小割，合併 s-t 兩點，使其強迫在同一個集合，不影響答案。

問題是卡在任意 s-t 的最小割，必須在盡可能快的時間內求出。網上都說算法神似最大生成樹 prim 算法，不過我想從遞歸中可以得到最後兩個入隊節點分別為 s-t，w[set A][s] >= w[set A][t] + w[s][t]，也就是說，s 流入 set A 的流量一定夠支持 w[set A][t]，並且約束在 w[set A][t] + w[s][t] 即為最小割。

［計算幾何］UVa 754 - Treasure Hunt－求更簡潔的作法。
埃及金字塔考古開挖，寶藏在其中一個密室，現在給金字塔的所有密室圖，求最少要爆破幾個牆壁才能從最外面進入寶藏所在的密室。

網路上有人使用半平面交，不斷地從寶藏所在之處的凸包，每次拿凸包邊的中點，外偏一點再找半平面交，直到碰到外界。但外偏多少才能保證會在另一個密室？這外偏的想法當然不錯，但想到誤差可能，還是先挑戰別的想法。精神還是繞著 Bfs 走。

把之前的 Point Location 拿出來用，先用 Partition Slab Map 頂替，用 Trapezoidal Map 可能就 ... 寫個半條命。得到可以支持 Point Location 的資料結構後，把 Dual graph 建造出來，就可以 Bfs 收工。

Shiang-Yun Yang \BSP tree/
January 16 at 5:23pm · Like
Huang I-Wen n只有30,而且他的平面圗是很多直線構成的，對於每個區塊，我們可以快速得知他是在每條線的正方向或負方向，所以每個區塊都可以用長度至多30的元素只含0,1的vector表示，每跨越一個邊就是vector上某個0變成1。
用這樣的概念的話可以很好想很好寫
January 16 at 7:39pm · Like
Huang I-Wen 不過我所謂的很好想好好寫...應該是在同時都曾經寫過我這方法和你那方法再來比較的話我是覺得這個方法比較好寫...第一次寫的話或許還是要思考許久
January 16 at 7:42pm · Like
Huang I-Wen 有很多實做的細節
January 16 at 7:52pm · Edited · Like
Huang I-Wen 時做的話可以對於每條直線，求出所有其他直線與他的交點，sort這些交點後，枚舉相鄰兩個交點的中點，求出該點對於其他所有直線是落在正區域或負區域，於是我們就知道只有該直線正負區域不同的兩個vector是相鄰的，於是就把所有邊建出來可以bfs了
January 16 at 7:56pm · Like
Shiang-Yun Yang 根據本蒟蒻的理解，會對每一個區域的邊上的中點，得到 vector(30) -> vector(30)，相當於從另一個區域爬到另一個區域的狀況。而 |vector(30)| <= 所有區域數，壓縮一下處理即可。
感謝大神 <(_ _)>
	// 20150101 - 20150225 Facebook Timeline.

	［UVa］1679 - Easy Geometry 開學第一題！
	在凸多邊形內部找一最大空白矩形。多邊形頂點數最多 10 萬個。
	三分內嵌三分再內嵌二分，幾何算法從函數觀點下手的有趣題目。

	〔UVa〕12415 - Digit Patterns
	讀入一個 regex，一個主字串 s，請問有不同的 i 滿足 s 的子字串 s[j...i] 符合 regex，套用 NFA 轉換成 DFA，可惜的是壓縮後狀態數還是太多，即使通過劉汝佳給的 small gift testdata，而且裡面倒數第二筆測資輸出有誤。當初學的時候就有這個疑問，果然狀態總數的增長非常大。

	所謂的動態 NFA 轉換 DFA 指得到底是什麼？又被劉汝佳坑了一題 QQQQQQQQ

	〔UVa〕210 - Concurrency Simulator
	作業系統排程 lock & unlock 模擬，去年某一天心血來潮寫，卻狂 WA。現在回過頭才發現對 quantum 的使用錯誤，在有限時間內，即使在有剩餘時間下，執行下一條單位操作，直到沒有剩餘時間，我卻用加法限制於 quantum 下，導致炸掉。

	題目中 "When an unlock is executed, any program at the head of the blocked queue is moved to the head of the ready queue"，為什麼只有一個 blocked queue 元素彈出，雖然在效率考量上是這樣，誤看成全部彈出，怪不得會一直 WA。但這樣所有模擬都會完結？

	〔全局最小割〕最小割 Stoer-Wagner 算法

	http://blog.sina.com.cn/s/blog_700906660100v7vb.html
	http://wenku.baidu.com/view/fdb484c3bb4cf7ec4afed08b.html

	主算法框架不難，隨著迭代將點數縮減，每次在 G(V, E) 找到其中一組 s-t 最小割，不管最小割 s-t 是否為答案，將 s-t 合併成一個點得到 G'(V', E')，繼續迭代。答案要不在剛剛求出的 s-t 要不在 G' 中，s-t 即假設兩點位於不同的集合，如果求出的不是最小割，合併 s-t 兩點，使其強迫在同一個集合，不影響答案。

	問題是卡在任意 s-t 的最小割，必須在盡可能快的時間內求出。網上都說算法神似最大生成樹 prim 算法，不過我想從遞歸中可以得到最後兩個入隊節點分別為 s-t，w[set A][s] >= w[set A][t] + w[s][t]，也就是說，s 流入 set A 的流量一定夠支持 w[set A][t]，並且約束在 w[set A][t] + w[s][t] 即為最小割。

	［計算幾何］UVa 754 - Treasure Hunt－求更簡潔的作法。
	埃及金字塔考古開挖，寶藏在其中一個密室，現在給金字塔的所有密室圖，求最少要爆破幾個牆壁才能從最外面進入寶藏所在的密室。

	網路上有人使用半平面交，不斷地從寶藏所在之處的凸包，每次拿凸包邊的中點，外偏一點再找半平面交，直到碰到外界。但外偏多少才能保證會在另一個密室？這外偏的想法當然不錯，但想到誤差可能，還是先挑戰別的想法。精神還是繞著 Bfs 走。

	把之前的 Point Location 拿出來用，先用 Partition Slab Map 頂替，用 Trapezoidal Map 可能就 ... 寫個半條命。得到可以支持 Point Location 的資料結構後，把 Dual graph 建造出來，就可以 Bfs 收工。

	Shiang-Yun Yang \BSP tree/
	January 16 at 5:23pm · Like
	Huang I-Wen n只有30,而且他的平面圗是很多直線構成的，對於每個區塊，我們可以快速得知他是在每條線的正方向或負方向，所以每個區塊都可以用長度至多30的元素只含0,1的vector表示，每跨越一個邊就是vector上某個0變成1。
	用這樣的概念的話可以很好想很好寫
	January 16 at 7:39pm · Like
	Huang I-Wen 不過我所謂的很好想好好寫...應該是在同時都曾經寫過我這方法和你那方法再來比較的話我是覺得這個方法比較好寫...第一次寫的話或許還是要思考許久
	January 16 at 7:42pm · Like
	Huang I-Wen 有很多實做的細節
	January 16 at 7:52pm · Edited · Like
	Huang I-Wen 時做的話可以對於每條直線，求出所有其他直線與他的交點，sort這些交點後，枚舉相鄰兩個交點的中點，求出該點對於其他所有直線是落在正區域或負區域，於是我們就知道只有該直線正負區域不同的兩個vector是相鄰的，於是就把所有邊建出來可以bfs了
	January 16 at 7:56pm · Like
	Shiang-Yun Yang 根據本蒟蒻的理解，會對每一個區域的邊上的中點，得到 vector(30) -> vector(30)，相當於從另一個區域爬到另一個區域的狀況。而 \|vector(30)\| <= 所有區域數，壓縮一下處理即可。
	感謝大神 <(_ _)>