第一階段 初級:第1周-第2周(共80題) | |||
項目 | 時間 | 必做題目 | |
基本算法 | 枚舉 | 第1周 | poj1753,poj2965 |
貪心 | poj1328,poj2109,poj2586 | ||
分治法 | |||
遞推 | |||
構造法 | poj3295 | ||
模拟法 | poj1068,poj2632,poj1573,poj2993,poj2996 | ||
圖算法 | 圖的深度優先周遊和廣度優先周遊 | 第1周 | |
最短路徑算法 | poj1860,poj3259,poj1062,poj2253,poj1125,poj2240 | ||
最小生成樹算法 | poj1789,poj2485,poj1258,poj3026 | ||
拓撲排序 | poj1094 | ||
二分圖的最大比對 | poj3041,poj3020 | ||
最大流的增廣路算法 | poj1459,poj3436 | ||
資料結構 | 串 | 第1周 | poj1035,poj3080,poj1936 |
排序 | poj2388,poj2299 | ||
簡單并查集的應用 | |||
哈希表和二分查找等高效查找法 | poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503 | ||
哈夫曼樹 | poj3253 | ||
堆 | |||
樹 | poj2513 | ||
簡單搜尋 | 深度優先搜尋 | 第2周 | poj2488,poj3083,poj3009,poj1321,poj2251 |
廣度優先搜尋 | poj3278,poj1426,poj3126,poj3087.poj3414 | ||
簡單搜尋技巧和剪枝 | poj2531,poj1416,poj2676,poj1129 | ||
動态規劃 | 背包問題 | 第2周 | poj1837,poj1276 |
型如下表的簡單DP | poj3267,poj1836,poj1260,poj2533,poj3176,poj1080,poj1159 | ||
數學 | 組合數學 | 第2周 | POJ3252,poj1850,poj1019,poj1942 |
數論 | poj2635, poj3292,poj1845,poj2115 | ||
計算方法 | poj3273,poj3258,poj1905,poj3122 | ||
計算幾何學 | 幾何公式 | 第2周 | |
叉積和點積的運用 | poj2031,poj1039 | ||
多邊型的簡單算法和相關判定 | poj1408,poj1584 | ||
凸包 | poj2187,poj1113 | ||
第二階段 中級:第3周-第4周(共85題) | |||
項目 | 時間 | 必做題目 | |
基本算法 | C++的标準模版庫的應用 | 第3周 | poj3096,poj3007 |
較為複雜的模拟題的訓練 | poj3393,poj1472,poj3371,poj1027,poj2706 | ||
圖算法 | 差分限制系統的建立和求解 | 第3周 | poj1201,poj2983 |
最小費用最大流 | poj2516,poj2516,poj2195 | ||
雙連通分量 | poj2942 | ||
強連通分支及其縮點 | poj2186 | ||
圖的割邊和割點 | poj3352 | ||
最小割模型 | poj3308 | ||
資料結構 | 線段樹 | 第3周 | poj2528,poj2828,poj2777,poj2886,poj2750 |
靜态二叉檢索樹 | poj2482,poj2352 | ||
樹狀樹組 | poj1195,poj3321 | ||
RMQ | poj3264,poj3368 | ||
并查集的進階應用 | poj1703,2492 | ||
KMP算法 | poj1961,poj2406 | ||
搜尋 | 最優化剪枝和可行性剪枝 | 第3周 | |
搜尋的技巧和優化 | poj3411,poj1724 | ||
記憶化搜尋 | poj3373,poj1691 | ||
動态規劃 | 較為複雜的動态規劃 | 第4周 | poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034 |
記錄狀态的動态規劃 | poj3254,poj2411,poj1185 | ||
樹型動态規劃 | poj2057,poj1947,poj2486,poj3140 | ||
數學 | 組合數學 | 第4周 | poj1286,poj2409,poj3270,poj1026 |
高斯消元法 | poj2947,poj1487, poj2065,poj1166,poj1222 | ||
機率問題 | poj3071,poj3440 | ||
GCD、擴充的歐幾裡德 | poj3101 | ||
計算方法 | poj2976,poj3150,poj3422,poj3070, poj3301 | ||
随機化算法 | poj3318,poj2454 | ||
雜題 | poj1870,poj3296,poj3286,poj1095 | ||
計算幾何學 | 坐标離散化 | 第4周 | |
掃描線算法 | poj1765,poj1177,poj1151,poj3277,poj2280,poj3004 | ||
邊形的核心 | poj3130,poj3335 | ||
幾何工具的綜合應用 | poj1819,poj1066,poj2043,poj3227,poj2165,poj3429 | ||
第三階段 進階:第5周-第6周(共59題) | |||
項目 | 時間 | 必做題目 | |
基本算法 | 代碼快速寫成 | 第5周 | poj2525,poj1684,poj1421,poj1048,poj2050,poj3306 |
保證正确性和高效性 | poj3434 | ||
圖算法 | 度限制最小生成樹和第K最短路 | 第5周 | poj1639 |
最短路,最小生成樹,二分圖,最大流問題的相關理論 | poj3155,poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446 | ||
最優比率生成樹 | poj2728 | ||
最小樹形圖 | poj3164 | ||
次小生成樹 | |||
無向圖、有向圖的最小環 | |||
資料結構 | trie圖的建立和應用 | 第5周 | poj2778 |
LCA和RMQ問題 | poj1330 | ||
雙端隊列和它的應用 | poj2823 | ||
左偏樹 | |||
字尾樹 | poj3415,poj3294 | ||
搜尋 | 較麻煩的搜尋題目訓練 | 第5周 | poj1069,poj3322,poj1475,poj1924,poj2049,poj3426 |
廣搜的狀态優化 | poj1768,poj1184,poj1872,poj1324,poj2046,poj1482 | ||
深搜的優化 | poj3131,poj2870,poj2286 | ||
動态規劃 | 需要用資料結構優化的動态規劃 | 第6周 | poj2754,poj3378,poj3017 |
四邊形不等式理論 | |||
較難的狀态DP | poj3133 | ||
數學 | 組合數學 | 第6周 | poj2888,poj2154 |
博奕論 | poj3317,poj1085 | ||
計算幾何學 | 半平面求交 | 第6周 | poj3384,poj2540 |
可視圖的建立 | poj2966 | ||
點集最小圓覆寫 | |||
對踵點 | poj2079 | ||
綜合題 | 第6周 | poj3109,poj |
高手給的訓練計劃
一般要做到50行以内的程式不用調試、100行以内的二分鐘内調試成功.acm主要是考算法的,主要時間是花在思考算法上,不是花在寫程式與debug上。
下面給個計劃你練練:
第一階段:練經典常用算法,下面的每個算法給我打上十到二十遍,同時自己精簡代碼,
因為太常用,是以要練到寫時不用想,10-15分鐘内打完,甚至關掉顯示器都可以把程式打
出來.
1.最短路(Floyd、Dijstra,BellmanFord)
2.最小生成樹(先寫個prim,kruscal要用并查集,不好寫)
3.大數(高精度)加減乘除
4.二分查找. (代碼可在五行以内)
5.叉乘、判線段相交、然後寫個凸包.
6.BFS、DFS,同時熟練hash表(要熟,要靈活,代碼要簡)
7.數學上的有:輾轉相除(兩行内),線段交點、多角形面積公式.
8. 調用系統的qsort, 技巧很多,慢慢掌握.
9. 任意進制間的轉換
第二階段:練習複雜一點,但也較常用的算法。
如:
1. 二分圖比對(匈牙利),最小路徑覆寫
2. 網絡流,最小費用流。
3. 線段樹.
4. 并查集。
5. 熟悉動态規劃的各個典型:LCS、最長遞增子串、三角剖分、記憶化dp
6.博弈類算法。博弈樹,二進制法等。
7.最大團,最大獨立集。
8.判斷點在多邊形内。
9. 差分限制系統.
10. 雙向廣度搜尋、A*算法,最小耗散優先.
第三階段:前兩個階段是打基礎,第三階段是鍛煉在比賽中可以快速建立模型、想新算法
。這就要平時多做做綜合的題型了。
1. 把oibh上的論文看看(大概幾百篇的,我隻看了一點點,呵呵)。
2. 平時掃掃zoj上的難題啦,别老做那些不用想的題.(中大acm的版主經常說我挑簡單的來
做:-P )
3. 多參加網上的比賽,感受一下比賽的氣氛,評估自己的實力.
4. 一道題不要過了就算,問一下人,有更好的算法也打一下。
5. 做過的題要記好
第一階段:練經典常用算法,下面的每個算法給我打上十到二十遍,同時自己精簡代碼,
因為太常用,是以要練到寫時不用想,10-15分鐘内打完,甚至關掉顯示器都可以把程式打
出來.
1.最短路(Floyd、Dijstra,BellmanFord)
2.最小生成樹(先寫個prim,kruscal要用并查集,不好寫)
3.大數(高精度)加減乘除
4.二分查找. (代碼可在五行以内)
5.叉乘、判線段相交、然後寫個凸包.
6.BFS、DFS,同時熟練hash表(要熟,要靈活,代碼要簡)
7.數學上的有:輾轉相除(兩行内),線段交點、多角形面積公式.
8. 調用系統的qsort, 技巧很多,慢慢掌握.
9. 任意進制間的轉換
第二階段:練習複雜一點,但也較常用的算法。
如:
1. 二分圖比對(匈牙利),最小路徑覆寫
2. 網絡流,最小費用流。
3. 線段樹.
4. 并查集。
5. 熟悉動态規劃的各個典型:LCS、最長遞增子串、三角剖分、記憶化dp
6.博弈類算法。博弈樹,二進制法等。
7.最大團,最大獨立集。
8.判斷點在多邊形内。
9. 差分限制系統.
10. 雙向廣度搜尋、A*算法,最小耗散優先.
初期:
一.基本算法:
(1)枚舉. (poj1753,poj2965)
(2)貪心(poj1328,poj2109,poj2586)
(3)遞歸和分治法.
(4)遞推.
(5)構造法.(poj3295)
(6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)
二.圖算法:
(1)圖的深度優先周遊(poj2488,poj3083,poj3009,poj1321,poj2251)
和廣度優先周遊.)(poj3278,poj1426,poj3126,poj3087.poj3414)
(2)最短路徑算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240,poj1511,poj1847,poj2387,
poj3268,poj3037,poj1502,poj1797,poj3615,poj3660,poj3013,poj3159,poj1275)
(3)最小生成樹算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026,poj1861,poj2395,poj2377,poj2421,poj1679,poj1751,poj1354,poj1251,poj3625,poj3522)
(4)拓撲排序 (poj1094)
(5)二分圖的最大比對 (匈牙利算法) (poj3041,poj3020,poj1274,poj3692,
poj2195,poj1466,poj1469,poj2239,poj1325,poj2771,poj1422,poj2594,poj1087)
(6)最大流的增廣路算法(EK算法,SAP算法,Dinic算法). (poj1459,poj3436,poj1273,poj3281,poj1087,poj1149 ,poj1698,poj2195,poj1815)
三.資料結構.
(1)串 (poj1035,poj3080,poj1936)
(2)排序(快排、歸并排(與逆序數有關)、堆排) (poj2388,poj2299)
(3)簡單并查集的應用. (poj1182,poj1456,poj1611,poj1988,poj2524,poj2236)
(4)哈希表和二分查找等高效查找法(數的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
(5)哈夫曼樹(poj3253)
(6)堆
(7)trie樹(靜态建樹、動态建樹) (poj2513poj3630,poj1204,
poj1056,hduoj1251,hduoj1247)
四.簡單搜尋
(1)深度優先搜尋 (poj2488,poj3083,poj3009,poj1321,poj2251)
(2)廣度優先搜尋(poj3278,poj1426,poj3126,poj3087.poj3414)
(3)簡單搜尋技巧和剪枝(poj2531,poj1416,poj2676,1129)
五.動态規劃
(1)背包問題. (poj1837,poj1276)
(2)型如下表的簡單DP(可參考lrj的書 page149):
1.E[j]=opt{D[i]+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最長公共子序列)
(poj3176,poj1080,poj1159)
3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優二分檢索樹問題)
六.數學
(1)組合數學:
1.加法原理和乘法原理.
2.排列組合.
3.遞推關系.
(POJ3252,poj1850,poj1019,poj1942)
(2)數論.
1.素數與整除問題
2.進制位.
3.同餘模運算.
(poj2635, poj3292,poj1845,poj2115)
(3)計算方法.
1.二分法求解單調函數相關知識.(poj3273,poj3258,poj1905,poj3122)
七.計算幾何學.
(1)幾何公式.
(2)叉積和點積的運用(如線段相交的判定,點到線段的距離等). (poj2031,poj1039)
(3)多邊型的簡單算法(求面積)和相關判定(點在多邊型内,多邊型是否相交)
(poj1408,poj1584)
(4)凸包. (poj2187,poj1113,poj1228,poj1794,poj2007,hoj1392,hoj1348,
hoj2202,hoj2215)
中級:
一.基本算法:
(1)C++的标準模版庫的應用. (poj3096,poj3007)
(2)較為複雜的模拟題的訓練(poj3393,poj1472,poj3371,poj1027,poj2706)
二.圖算法:
(1)差分限制系統的建立和求解. (poj1201,poj2983,poj1364,poj3169,poj3159
,poj1716,poj1275,zoj1260,zoj1420,zoj1455) (利用最短路Bellman_Ford和SPFA算法)。
(2)最小費用最大流(poj2516,,poj2195)
(3)雙連通分量(poj2942,poj3694,poj3177)
(4)強連通分支及其縮點.(poj2186)
(5)圖的割邊和割點(poj3352)
(6)最小割模型、網絡流規約(poj3308, )
三.資料結構.
(1)線段樹(poj2528,poj2828,poj2777,poj2886,poj2750,poj3277,poj3225,
poj2482,poj1177,poj1029,poj2182,poj2104,poj2761,poj2140,poj2155,poj2195,
hoj1166,hoj1754, hoj1698, hoj 1394 , hoj2795, hoj1540, hoj2781,
hoj3016, hoj1542, hoj1255, hoj1828,hoj1823)
(2)靜态二叉檢索樹. (poj2482,poj2352)
(3)樹狀樹組(poj1195,poj3321)
(4)RMQ. (poj3264(sample),poj3368(change something) 2823(滾動數組))
(5)并查集的進階應用. (poj1703,2492)
(6)KMP算法. (poj1961,poj2406)
四.搜尋
(1)最優化剪枝和可行性剪枝
(2)搜尋的技巧和優化 (poj3411,poj1724)
(3)記憶化搜尋(poj3373,poj1691)
五.動态規劃
(1)較為複雜的動态規劃(如動态規劃解特别的旅行商問題等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
(2)記錄狀态的動态規劃. (POJ3254,poj2411,poj1185)
(3)樹型動态規劃(poj2057,poj1947,poj2486,poj3140)
六.數學
(1)組合數學:
1.容斥原理.
2.抽屜原理.
3.置換群與Polya定理(poj1286,poj2409,poj3270,poj1026).
4.遞推關系和母函數.
(2)數學.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.機率問題. (poj3071,poj3440)
3.GCD、擴充的歐幾裡德(中國剩餘定理) (poj3101)
(3)計算方法.
1.0/1分數規劃. (poj2976)
2.三分法求解單峰(單谷)的極值.
3.矩陣法(poj3150,poj3422,poj3070)
4.疊代逼近(poj3301)
(4)随機化算法(poj3318,poj2454)
(5)雜題.
(poj1870,poj3296,poj3286,poj1095)
七.計算幾何學.
(1)坐标離散化.
(2)掃描線算法(例如求矩形的面積和周長并,常和線段樹或堆一起使用).
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
(3)多邊形的核心(半平面交)(poj3130,poj3335)
(4)幾何工具的綜合應用.(poj1819,
poj1066,poj2043,poj3227,poj2165,poj3429)
進階:
一.基本算法要求:
(1)代碼快速寫成,精簡但不失風格
(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)
(2)保證正确性和高效性. poj3434
二.圖算法:
(1)度限制最小生成樹和第K最短路. (poj1639)
(2)最短路,最小生成樹,二分圖,最大流問題的相關理論(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
(3)最優比率生成樹. (poj2728)
(4)最小樹形圖(poj3164)
(5)次小生成樹.
(6)無向圖、有向圖的最小環
三.資料結構.
(1)trie圖的建立和應用. (poj2778,poj 1204字典樹 ZOJ1109 HDU1251 PKU1204 HDU1075)
(2)LCA和RMQ問題(LCA(最近公共祖先問題) 有離線算法(并查集+dfs) 和 線上算法
(RMQ+dfs)).(poj1330)
(3)雙端隊列和它的應用(維護一個單調的隊列,常常在動态規劃中起到優化狀态轉移的
目的). (poj2823)
(4)左偏樹(可合并堆).
(5)字尾樹(非常有用的資料結構,也是賽區考題的熱點).
(poj3415,poj3294)
四.搜尋
(1)較麻煩的搜尋題目訓練(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)
(2)廣搜的狀态優化:利用M進制數存儲狀态、轉化為串用hash表判重、按位壓縮存儲狀态、雙向廣搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)
(3)深搜的優化:盡量用位運算、一定要加剪枝、函數參數盡可能少、層數不易過大、可以考慮雙向搜尋或者是輪換搜尋、IDA*算法. (poj3131,poj2870,poj2286)
五.動态規劃
(1)需要用資料結構優化的動态規劃.
(poj2754,poj3378,poj3017)
(2)四邊形不等式理論.
(3)較難的狀态DP(poj3133)
六.數學
(1)組合數學.
1.MoBius反演(poj2888,poj2154)
2.偏序關系理論.
(2)博奕論.
1.極大極小過程(poj3317,poj1085)
2.Nim問題.
七.計算幾何學.
(1)半平面求交(poj3384,poj2540)
(2)可視圖的建立(poj2966)
(3)點集最小圓覆寫.
(4)對踵點(poj2079)
八.綜合題.
(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)
資料結構
組織結構
二叉堆
左偏樹
二項樹
勝者樹
跳躍表
樣式圖示
斜堆
treap
統計結構
樹狀數組
虛二叉樹
線段樹
矩形面積并
圓形面積并
關系結構
Hash表
并查集
路徑壓縮思想的應用
STL中的資料結構
vector
deque
set / map
1:數學
1.1:數論
1.1.1:中國剩餘定理
1.1.2:歐拉函數
1.1.3:歐幾裡得定理
1.1.3.1:歐幾裡得定理
1.1.3.2:擴充歐幾裡得
1.1.4:大數分解與素數判定
1.1.5:佩爾方程
1.2:組合數學
1.2.1:排列組合
1.2.2:容斥原理
1.2.3:遞推關系和生成函數
1.2.4:Polya計數法
1.2.4.1:Polya計數公式
1.2.4.2:Burnside定理
1.3:計算方法
1.3.1:二分法
1.3.1.1:用矩陣加速的計算
1.3.2:疊代法
1.3.3:三分法
1.3.4:解線性方程組
1.3.4.1:LUP分解
1.3.4.2:高斯消元
1.3.5:解模線性方程組
1.3.6:定積分計算
1.3.7:多項式求根
1.3.8:周期性方程
1.3.9:線性規劃
1.3.10:快速傅立葉變換
1.3.11:随機算法
1.4:構造方法
1.4.1:N皇後構造解
1.4.2:幻方的構造
1.4.3:滿足一定條件的hamilton圈的構造
1.5:特殊的數
1.5.1:Catalan數
1.5.2:Stirling數
1.5.3:斐波拉契數
1.5.4:調和數
1.5.4:連分數
2:資料結構
2.1:棧,隊列,連結清單
2.2:哈希表
2.3:堆,優先隊列
2.3.1:左偏樹
2.4:二叉查找樹
2.4.1:Treap
2.4.2:伸展樹
2.5:并查集
2.6:平衡二叉樹
2.7:線段樹
2.7.1:一維線段樹
2.7.2:二維線段樹
2.8:樹狀數組
2.8.1:一維樹狀數組
2.8.2:N維樹狀數組
2.9:字典樹
2.10:字尾數組
2.11:塊狀連結清單
3:圖論
3.1:圖
3.1.1.:廣度優先周遊
3.1.2.:深度優先周遊
3.1.3.:拓撲排序
3.1.4.:割邊割點
3.1.5.:強連通分量
3.1.5:2-SAT問題
3.1.6.:歐拉回路
3.1.7.:哈密頓回路
3.2.:最小生成樹
3.2.1.:Prim算法
3.2.2.:Kruskal算法
3.2.3.:Sollin算法
3.2.4.:次小生成樹
3.2.5.:第k小生成樹
3.2.6.:最優比例生成樹
3.2.7.:最小樹形圖
3.2.8.:最小度限制生成樹
3.2.9.:平面點的歐幾裡德最小生成樹
3.2.10.:平面點的曼哈頓最小生成樹
3.2.11.:最小平衡生成樹
3.3.:最短路徑
3.3.1.:有向無環圖的最短路徑->拓撲排序
3.3.2.:非負權值權重圖的最短路徑->Dijkstra算法
3.3.3.:含負權值權重圖的最短路徑->Bellmanford算法
3.3.4.:含負權值權重圖的最短路徑->Spfa算法
3.3.5.:全源最短路弗洛伊德算法Floyd
3.3.6.:全源最短路Johnson算法
3.3.7.:次短路徑
3.3.8.:第k短路徑
3.3.9.:差分限制系統
3.3.10.:平面點對的最短路徑(優化)
3.3.11.:雙标準限制最短路徑
3.4.:最大流
3.4.1.:增廣路->Ford-Fulkerson算法
3.4.2.:預推流
3.4.3.:Dinic算法
3.4.4.:有上下界限制的最大流
3.4.5.:節點有限制的網絡流
3.4.6.:無向圖最小割->Stoer-Wagner算法
3.4.7.:有向圖和無向圖的邊不交路徑
3.4.8.:Ford-Fulkerson疊加算法
3.4.9.:含負費用的最小費用最大流
3.5.:比對
3.5.1.:Hungary算法
3.5.2.:最小點覆寫
3.5.3.:最小路徑覆寫
3.5.4.:最大獨立集問題
3.5.5.:二分圖最優完備比對Kuhn-Munkras算法
3.5.6.:一般圖的最大基數比對
3.5.7.:一般圖的賦權比對問題
4:搜尋
5:計算幾何:
5.1基本公式
5.1.1:叉乘
5.1.2:點乘
5.1.3:常見形狀的面積、周長、體積公式
5.2:線段
5.2.1:判斷兩線段(一直線、一線段)是否相交
5.2.2:求兩線段的交點
5.3:多邊形
5.3.1:判定凸多邊形,頂點按順時針或逆時針給出,(不)允許相鄰邊共線
5.3.2:判點在凸多邊形内或多邊形邊上,頂點按順時針或逆時針給出
5.3.3:判點在凸多邊形内,頂點按順時針或逆時針給出,在多邊形邊上傳回0
5.3.4:判點在任意多邊形内,頂點按順時針或逆時針給出
5.3.5:判線段在任意多邊形内,頂點按順時針或逆時針給出,與邊界相交傳回1
5.3.6:多邊形重心
5.3.7:多邊形切割(半平面交)
5.4:三角形
5.4.1:内心
5.4.2:外心
5.4.3:重心
5.4.4:垂心
5.4.5:費馬點
5.5:圓
5.5.1:判直線和圓相交,包括相切
5.5.2:判線段和圓相交,包括端點和相切
5.5.3:判圓和圓相交,包括相切
5.5.4:計算圓上到點p最近點,如p與圓心重合,傳回p本身
5.5.5:計算直線與圓的交點,保證直線與圓有交點
5.5.6:計算線段與圓的交點可用這個函數後判點是否線上段上
5.5.7:計算圓與圓的交點,保證圓與圓有交點,圓心不重合
5.5.8:計算兩圓的内外公切線
5.5.9:計算線段到圓的切點
5.6:經典問題
5.6.1:平面凸包
5.6.2:三維凸包
5.6.3:Delaunay剖分/Voronoi圖