[Counting Sort, Radix Sort] 計數排序, 基數排序

 Counting Sort是一種效率很高的排序方式，複雜度為$\ord{n+k}$，其中$k$是Bucket的大小，由此可知僅限於整數且數字範圍不能太大。根據觀察在很多應用中會有對物件以編號大小進行排序的行為，在這方面應該能做到很大的加速。

另外一個問題是Counting Sort雖然簡單，很多人甚至可以自己想到實作方法，但這也導致了標準的作法常常被人忽略。因此這裡就來給大家展示標準的Counting sort：

參數的解釋如下：

• First, Last:
  和std::sort的定義一樣，需要排序的範圍，注意不一定要是random access iterator。
• BucketFirst, BucketLast:
  Counting Sort正統的實作方式會有一個正整數陣列作為Bucket，考量到各種應用所以這裡接傳Bucket的範圍進來能做的優化會比較多，必須要是random access iterator。
• OutputFirst:
  Counting Sort的output是直接將input存到另一個陣列中，因此OutputFirst指的是Output陣列的開頭，必須要是random access iteator，且要注意output的空間是足夠的。這邊將input存進output時是用std::move的方式，如果想要保留原本input的話可以將其拿掉。
• Key:
  這是一個函數，Key(x)必須要回傳一個0~(BucketLast-BucketFirst-1)的正整數作為被排序物件x的關鍵值。

有了Counting sort，Radix Sort就比較好解釋了。首先正統的Counting sort是stable sort，所以Key值相同的東西排序前後的先後順序是不變的。因此可以透過多次的Counting Sort來完成一些原本Counting Sort無法完成的事情。

以整數(int, -2147483648~2147483647)排序為例，可以先針對第十億位做為Key進行排序，接著再對第一億位做為Key、第一千萬位做為Key...直到十位數、個位數作為Key，最後再以正負號最為Key進行排序，這樣就可以完成一般範圍的整數排序。

實際上一般不會這樣用，通常是用在有多個Key值的情況，以下面的程式碼來說，可以自行執行看看花費的時間有多少：

[Discretizer] 離散化器

離散化是演算法競賽常用的操作，在各種實際問題上也能看到其應用。最基本的情況，是對於n個可排序的元素，製造一個map使得它們可以和自己的名次一一對應，但通常的應用中這n個元素確定之後就不太會有增減的動作，因此可以存到vector中排序去除重複的部分，搜索的部分就用二分搜尋來取代。

[Multiple line segment intersection] Bentley–Ottmann 演算法

 基本上這個問題就是給你一些線段(格式通常為兩個端點)，你要找出這些線段的交點。直觀的做法兩兩進行計算會花上$\ord{n^2}$的時間，但大多數的情況下交點不會很多。為了解決這個問題，修改自Shamos–Hoey演算法的Bentley–Ottmann演算法可以在$\ord{(n+k)\log n}$的時間內找出所有交點，其中$k$是交點數量。

這裡附上實作時需要用到的基本資料結構：

演算法使用掃描線進行。掃描線是一條垂直線從左邊掃到右邊(有些實作是水平線從上面掃到下面)，並且在遇到事件點的時候進行相關處理。

線段的兩端點以及交點都作為事件點被紀錄在最終結果中。對於每個事件點$P$，我們會計算三個集合：

• U集合：所有以$P$為起始點的線段集合
• C集合：所有包含$P$的線段集合
• L集合：所有以$P$為結束點的線段集合

當然要先保證每條線段的起始點移動會在結束點的左方，只要得到線段後稍微判斷一下就可以做到了。每個事件點找出這三個集合後就可以很容易的判斷相交資訊，但要注意的是會有以下的退化情形：

• 線段退化成點：這種情況該點的U和L都會包含該線段。
• 兩線段重合：只有重合處的兩端點會被紀錄為事件點，可以根據UCL判斷出是否線段重合
• 垂直線段：排序點和線段時如果x一樣就按照y來比較
  

最後是掃描線的資料結構，需要一棵平衡的BST根據當前掃描線和各個線段切點的y值進行排序，但這件事是可以用STL做到的！我們把當前事件點傳進比較函數裡面進行計算，因為在任何一個時刻BST中的資料都是根據當前的比較函數由小排到大的，應該不算undefined behavior。另外該演算法的浮點數誤差很大，建議使用時套上處理誤差的模板或是直接用分數計算：

最後是測試的部分，以下圖做為測試範例：

將該圖轉換成我們接受的input如下：

10

-2 7 2 0

-2 7 -2 0

-2 6 2 5

-2 6 2 2

-2 4 2 7

-2 4 2 2

-2 4 4 1

-2 0 2 2

0 1 0 1

0 3 4 1

最後附上測試程式碼，需要的話可以自己執行看看：

[ Minimum Spanning Tree, kruskal, prim ] 最小生成樹經典演算法

以前覺得這應該是很簡單的東西，但我發現網路上使用priority_queue的prim演算法相關程式碼我覺得寫不好，我就把我自己的放上來。這裡順便也放上kruskal的程式碼。

prim $\ord{\left(\abs{V}+\abs{E}\right)\log{\abs{V}}}$:
kruskal $\ord{\abs{V}+\abs{E}\log{\abs{E}}}$:

[ Delaunay Triangulation ] Delaunay 三角剖分

我高中的時候在morris的網站第一次看到這個東西，那個時候就很想試著寫出來看看，但那時候英文很不好所以不會找資料就沒有成功。直到今年的NPSC，聽說台大出了一題找Voronoi Diagram的題目沒有人寫出來，於是我就想挑戰看看，寒假開始之後就認真研讀相關資料，終於在前幾天完成了隨機增量法以及分治法的模板。

先來說說甚麼是三角剖分 Triangulation 吧！假設平面上散布很多不重複的點，現在用一些線段將這些點連成許多的三角形，滿足所有三角形的內部不會有其他點，而且三角形的數量越多越好，這就是一個三角剖分。

Delaunay Triangulation是一種特殊的三角剖分，滿足所有的三角形其外接圓中不會出現其他的點，這樣的性質會使得所有三角形中最小的角盡量大，而且最重要的是它是 Voronoi Diagram 的對偶圖，Voronoi Diagram 直接求的話很容易有浮點誤差而且程式也不好寫，因此從Delaunay Triangulation直接轉換過去會更加方便。

還有一個很重要的點，透過Delaunay Triangulation 的邊集合可以找出平面歐幾里得距離最小生成樹。

這裡我先給出點的資料結構，方便接下來的講解：

一般來說找出 Delaunay Triangulation 的其中一個操作是要判斷一個點是不是在一個三角形的外接圓內，但直接去求外接圓圓心會有浮點誤差，因此有一個作法是將所有點投影到三維的拋物線曲面中，也就是下圖的碗狀曲面，會發現把一個圓投影上去之後，該圓會落在一個平面上，圓內的點會在平面下面，圓外的點會在平面上面，這樣就可以利用一些處理三維幾何的技術就可以避免浮點誤差的判斷點是否在外接圓內了。

範例程式碼中點在圓內輸出1，圓外輸出-1，圓上輸出0：

當然實作時並不會真正的寫一個三維點的資料結構，這樣程式碼會比較長。

Delaunay Triangulation 我所知道的有兩種，分別是隨機增量法以及分治法。隨機增量法再點隨機加入的時候複雜度是$\ord{n\log n}$，分治法則是穩定$\ord{n\log n}$，但我的實作分治法的效能是隨機增量法的三倍快。由於兩種做法都已經有詳細教學了這裡就不用文字敘述。

1. 隨機增量法教學在《Computational Geometry - Algorithms and Applications》書中有提到，該書有中文版
2. 分治法教學請點該網站連結

這裡附上程式碼，順帶一提morris的分治法好像在某些測資會因為三點共線爛掉

隨機增量法：

分治法：

[ Cyclic Longest Common Subsequence ] 環狀最長共同子序列

相信會看我發的文的人應該多少都知道LCS(最長共同子序列)是什麼吧？對於這樣的問題很早以前就有人提出$\ord{nm}$的方法了。
現在如果將問題中的字串改成頭尾相接環狀的字串，我們稱其最長共同子序列為CLCS，例如：

設A,B為頭尾相接環狀字串

A = "aabaa" , B = "aaabb"

CLCS(A,B) = "aaab"

像這樣的問題要怎麼解呢？剛好codeforces上面就有一題：http://codeforces.com/gym/100203/problem/B

為了解決這一題，查閱了不少奇怪的文章，最後給我找到了這篇論文：Solving Cyclic Longest Common Subsequence in Quadratic Time

對於CLCS提出了$\ord{nm}$的演算法，在這裡附上該演算法的實作：

作法大致上是將b字串變成原來的兩倍，然後做一般的LCS，但在過程中要注意更新答案的順序。接著修改DP來源表格，每次將來源表格的第一個row刪掉(reRoot函數)，然後計算當前的答案。

當我AC這一題後，我看到了一個非常驚人的作法，也是用DP複雜度是$\ord{nm}$，但是我目前還無法完全理解為何這樣是可行的，而且這樣的做法我也不知道如何回溯找出一組解，只能知道CLCS的長度，希望路過的大大們能提供想法：

[ lower convex hull self-balancing binary search tree ] 下凸包平衡樹

下凸包平衡樹是一個動態維護下凸包的資料結構，他至少能在$\ord{\log n}$時間完成以下兩個操作：

1. 查詢 point(x,y) 是否被包含於下凸包中
2. 將 point(x,y) 加入至下凸包中，然後將不位於下凸包頂點上的點刪除

由於繼承自C++ STL map，因此所有能對map用的操作都能被使用，對於那些會改動map資料的操作請小心使用避免影響到凸包的正確性，例如operator[]就盡量不要使用。

對於某些動態規劃問題需要用凸包斜率優化時應該非常有用，有空會補上專門用來動態做斜率優化的版本