進度

1. USACO
   Ch. 3 完成於 2010-09-30

---

算法學習與實踐:

1. Separating Axis Theorem (2010-02-18)
   Verified: UVA 11275, ...
2. 半平面交 - Expected O(N) 隨機算法 (2010-02-24)
   Verified: POJ 3130, ...
3. 網絡最大流 - Dinic 算法 (2010-02-27)
   Verfied: POJ 3649, ...
4. 網絡最大流/最小割應用 - 最大封閉權子圖 (2010-03-13)
   Verfied: POJ 2987, ...
5. NIM @ CSC3270 (2010-03-21)
   Verified: POJ 3537, ...
6. Discrete Logging (MOD P) - Baby-step, Giant-step Algorithm (2010-06-17)
   Verified: POJ 2417
7. 半平面交 - O(N lg N) ZZY 算法 (2010-06-29)
   Verified: POJ 1279
   Wrong Answer: UVa 11756
8. 旋轉卡殼 (Rotating Calipers) (2010-07-21)
   凸多邊形間最短距離 - O(N+M) - Verified: POJ 3608
   凸多邊形間最大距離 - O(N+M)
   凸多邊形直徑 - O(N) - Verified: POJ 2187
9. Farey Sequence - O(N lg N) (2010-??-??)
   1) ICPC 4275
10. Point in Convex Polygon - 純粹二分 - O(lg N) (2010-10-10)
    Verified: SGU 253
11. Two-Phase Method - Phase I (2010-11-14)
    Verified: PKU 3477
12. Two-Phase Method - Phase 1+2 (2010-11-27)
    Verified: ICPC 4027
13. 三維線段最近距離 (2010-12-09)
    Verified: PKU 2913
14. O(3^N) 枚舉所有集合的子集 (2011-02-06)
    Verified: SRM 491 600

---

Online Judge (單題練習):

Solved:

• Ural 1775 Space Bowling 2D-Geometry, Separating Axis Theorem
• PKU 2731 ACM(ACronymMaker) DP, Memorized Search
• Ural 1464 Light 2D-Geometry, Visibility, Sweep-line Algorithm
• Ural 1058 Chocolate 撒點水過
• ZJU 3376 Safest Points 廣搜
• ZJU 3379 Master Spark 極角排序, 線性數描
• Ural 1340
• PKU 3378
• ICPC 4275
• PKU 2729
• PKU 1066
• ICPC 4025
• ICPC 3667
• ICPC 2947
• ICPC 2929
• PKU 3747
• UVa 11422
• PKU 1743
• PKU 3608
• HDU 3644
• Codeforces 30E
• Codeforces 60E
• SRM 498 1000 Knapsack + Inclusion-Exclusion + nCr
• SRM 499 1000 SCC + Longest Path on DAG + nCr
  C(33,3) * 50
• SRM 481 1000 Bipartite-Matching + BSearch + nCr
  C(15,7) * 16^3 * log(32*10^6)
• PKU 2903 3D Geom, 2D Grid + BFS

TODO's:

• HDU 3558
• HDU 3227
• UVa 11815
• PKU 3285
• Ural 1265
• ZJU 3378
• PKU 3643
• PKU 3474
• PKU 2401
• AIZU 2114
• ICPC 3193
• UVa 11756
• HUST 2017
• PKU 2069
• PKU 3521
• UVa 746
• PKU 2913

---

2009 年學習進度（比較慢 -_-）：

09 Jan	Monotone Chain PKU 2823
10 Jan	Monotone Chain (Con't) PKU 2019
11 Jan	3D-Block-Rotation UVa 197
16 Feb	1/0 Weighted Graph -> BFS UVa 11573
19 Feb	Inclusion-Exclusion ICPC 4184
21 Feb	Segment Tree (Static; RMQ) PKU 2104
23 Feb	Trie (Shortest Prefix) PKU 2001
27 Feb	Trie (Disk Tree) PKU 1760
02 Mar	Size of SubTree by BFS ICPC 4390
04 Mar	RMQ - ＜O(N), O(sqrt(N))＞ PKU 3264
24 Apr	Classical Searching PKU 1011
26 Apr	Expected Value - Probability PKU 3156
18 May	Median Heap - O(Lg N) Query UVa 10107
22 May	Circular Convex Hull PKU 3405
27 May	Point In/Out-side Concave Polygon PKU 2966
2 June	Radix Sort ＜O(N*LgbN)＞ PKU 2388
2 June	*Backward DP - Coin Change UVa 11517
4 June	DP - Coins - O＜MN＞ PKU 1742
8 June	Constrained Difference - Shortest Path ICPC 4242
10 June	Constrained Difference - Shortest Path PKU 1364
11 June	N Queen - Heuristic Repair ICPC 3388
13 June	General Form of Pythagoras Triple UVa 106
16 June	*SPFA ICPC 4435
26 June	*Winding Number Algorithm (Point In/Out Polygon) PKU 2462
29 June	*SLF : SPFA Optimization PKU 3159
02 July	*Rotating Caliper - Farthest Pair PKU 2187
02 July	*Rotating Caliper - Smallest Bounding Rectangle UVa 10173
21 Nov	*Suffix Array - Application of Height Function ICPC 4513