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

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

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

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

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

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

  閱讀全文