PKU 2416 Return of the Jedi

題意：

在平面上，給定 N (≤ 10) 個圓（任何兩圓不相交／觸碰）
及 A、B 兩點

求最短 A 到 B 路徑（不得進入任何圓形內，但可以觸碰）的長度

---

應用知識：

此題基本上是一道 2D Geometry Exercise
只是在 公式推導 及 處理 Boundary Cases 時要比較小心...

1. 圓到圓切線（全４種）
2. 點到圓切線
   
3. 判斷 線段／圓 交點
   
4. 最短路算法

2. 的計算可透過 1. 完成
── 把 點 看為 半徑 = 0 的圓

---

ICPC 4455 Suffix-Replacement Grammars

ICPC 4455 Suffix-Replacement Grammars

[World Finals 2009 - Problem K]

題意：
現給定 N (<=100) 項規則，每項
形式為： X→Y（其中 X 和 Y 等長）
意義是：若字串的後綴為 X，則可花費用 1 ，將後綴替換成 Y。

求由字串 S 轉換至 T 最短路*。（其中 S 和 T 等長）

所有字串長度最多為 20。

[* 即 最小費用，使用 "最短路" 此詞是因為描術更直觀]

---

樣例：
規則：
BC → CD
BC → CA
BCD → CCZ
A → C

S = BBA
T = CCZ

　 BBA
→ BBC (應用 "A → C")
→ BCD (應用 "BC → CD")
→ CCZ (應用 "BCD → CCZ")

Answer: 3