Posted on 2010-03-10 13:05
王之昊 閱讀(626)
評論(0) 編輯 收藏 引用 所屬分類:
pku
考慮掃描線,選擇一個圓的最左點和最右點作為事件點.然后用一條豎直線從左到右掃一遍.
維護一個數據結構,里面保存著和掃描線相交的powerful 圓.
如果一個事件是某圓的最右點,并且該圓在數據結構中,就意味著要把這個圓刪掉.
如果一個事件是某圓的最左點,當它不被其他圓包含時,就意味著可能要把它加入到我們的數據結構中,
怎么檢查它有沒有被其他圓包含呢?我們的數據結構里的圓都是一些 powerful 圓,他們互不相交,也就是
說他們在當前的掃描線上占的區間也互不相交, 如果我們只是記錄圓心在掃描線的投影, 把高的投影稱為前,
把低的投影低稱為后,那么可能與當前圓發生關系的只是它的前一個圓,后一個圓.
然后來決定數據結構,要滿足插入一個圓,刪除一個圓,詢問前一個圓,詢問后一個圓.map就可以勝任了.