[隨筆] 修煉 I - Rotating Caliper

這幾天正在忙 research
亦有一邊做題目

不過要下決心不做水題了... orz

這陣子...

Chin 經已把 Farey Sequence 弄明白
CTLi 則在攻 Game 及 插頭DP 的題目
Joe 也剛剛應用 Sweep Line Algorithm 把 Chengdu 2008 的 題D 幹掉

我呢...?
也許是時候開始研究 旋轉卡殼(Rotating Caliper) 及 凸多邊形(Convex Polygon) 了

感覺這個 topic 的資訊量挺大的 (見下) ...

---

幾個搜回來的鏈接：

1. Rotating Caliper 始創者／發揚光大者 (好似係)
   
2. 旋轉卡殼 與 凸多邊形 (By ACMaker)
3. 凸多邊形相關的題 (By imlazy)
4. 因為選擇,所以喜歡! 計算幾何 專題 (By Hailer(?))
   

---

題目（待追加）：

1. UVa 476 Polygon Visibility
2. PKU 3608 Bridge Across Islands
   Minimum distance between 2 disjoint convex polygons - 2010-07-21
   

---

旋轉卡殼的應用（轉貼）：

• Computing distances
  
  
  • The diameter of a convex polygon
  • The width of a convex polygon
  • The maximum distance between 2 convex polygons
  • The minimum distance between 2 convex polygons [2010-07-21]
• Enclosing rectangles
  
  • The minimum area enclosing rectangle
  • The minimum perimeter enclosing rectangle
• Triangulations
  
  • Onion triangulations
  • Spiral triangulations
  • Quadrangulations
• Properties of convex polygons
  
  • Merging convex hulls
  • Finding common tangents
  • Intersecting convex polygons
  • Critical support lines
  • Vector sums of convex polygons
• Thinnest transversals
  
  • Thinnest-strip transversals

---

Offtopic：推薦 POJ Monthly 某道關於 拓撲順序 (Topological sort) 的題目

• PKU 3687 題目鏈接
• PKU 3687 解題報告 (By imlazy)