摘要: 很好的基礎題，判斷直線相交的情況。要注意精度。判斷平行和重合時，用整數運算比較精確。剩下的事就是解出交點了。

  閱讀全文      摘要: 樸素做法是 O(n^3) 的，超時。我的做法是枚舉每個點，然后求其它點和它連線的斜率，再排序。這樣就得到經過該點的直線最多能經過幾個點。求個最大值就行了。復雜度是 O(n^2logn) 的。把排序換成 hash，可以優化到 O(n^2)。

  閱讀全文      摘要: 應用平面圖的歐拉定理：V + F - E = 2
兩兩線段求交，得到交點數 V，然后判斷每個交點落在幾條邊上，如果一個點在一條邊上，這條邊就分裂成兩條邊，邊數加 1。這樣得到邊數 E。最后直接用歐拉定理解得 F。

  閱讀全文      摘要: 題目給出 n 個矩形，要求它們的面積并。具體做法是離散化。先把 2n 個 x 坐標排序去重，然后再把所有水平線段（要記錄是矩形上邊還是下邊）按 y 坐標排序。最后對于每一小段區間 (x[i], x[i + 1]) 掃描所有的水平線段，求出這些水平線段在小區間內覆蓋的面積。總的時間復雜度是 O(n^2)。利用線段樹，可以優化到 O(nlogn)。

  閱讀全文      摘要: 先求凸包，答案是凸包周長 + 2πl。因為簡單多邊形的轉角是360度，所以加上一個圓的周長。

  閱讀全文      摘要: 簡單題，直接模擬即可

  閱讀全文      摘要: 公式很容易猜出，見代碼

  閱讀全文      摘要: pku 部分計算幾何題目列表

  閱讀全文      摘要: 先把矩形擴大 sqrt(2) 倍，轉化為整點問題。然后逐個求出每個矩形的坐標。
對于每個矩形分別求出在它之上的矩形覆蓋的區間大小 t1，和包括它本身以及在它之上的矩形覆蓋的區間大小 t2
若 t1 == t2，則該矩形被遮蓋。

  閱讀全文      摘要: 建立一個虛點（權為無窮大），從它到每個入度為 0 的點都連一條邊，然后做樹型DP。
先遞歸算出子結點的 f 值，然后用背包的方法計算父結點的 f 值。

  閱讀全文