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

然后來決定數(shù)據(jù)結(jié)構(gòu),要滿足插入一個圓,刪除一個圓,詢問前一個圓,詢問后一個圓.map就可以勝任了.