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