摘要: 動態規劃總結 by Amber

  閱讀全文      摘要: 問題是求平面歐幾里德最小生成樹的第n - k小邊。
平面歐幾里德最小生成樹是經典問題，可以做到O(nlogn)。具體做法是先對平面點進行三角剖分，時間復雜度是O(nlogn)，三角剖分的邊就是可能的在最小生成樹的邊。因為是平面圖，所以有O(n)條邊，在其上應用 Kruscal 算法即可。

  閱讀全文      摘要: 漫談扭結

  閱讀全文      摘要: 此問題可轉化為求三角形垂心。我的做法是設垂心坐標為(x, y)，然后利用垂直關系解方程。

  閱讀全文      摘要: Ubuntu 6.10 @ Dell XPS M1210 安裝手記

  閱讀全文      摘要: 一首小詩……

  閱讀全文      摘要: 平面點的曼哈頓最小生成樹

  閱讀全文      摘要: 簡單計算幾何，我的做法是列出所有可能的切法（一共18種），求最優值。

  閱讀全文      摘要: 構造所有的線段，然后枚舉每對水平－豎直線段，求交點，然后計算四邊形面積，求最大值。

  閱讀全文      摘要: 強烈推薦此題！
狀態壓縮DP的好題！
分析見內

  閱讀全文