數(shù)據(jù)結(jié)構(gòu)的選擇與算法效率

1、數(shù)據(jù)結(jié)構(gòu)的選擇與算法效率從IOI98試題PICTURE談起- PAGE 36 -IOI99中國(guó)集訓(xùn)隊(duì)優(yōu)秀論文選IOI99中國(guó)集訓(xùn)隊(duì)優(yōu)秀論文選- PAGE 35 -IOI99中國(guó)集訓(xùn)隊(duì)優(yōu)秀論文選- PAGE 21 -數(shù)據(jù)結(jié)構(gòu)構(gòu)的選擇擇與算法法效率從IIOI998試題題PICCTURRE談起起 【關(guān)鍵字字】數(shù)據(jù)結(jié)構(gòu)構(gòu)的選擇擇 線性結(jié)結(jié)構(gòu) 樹形形結(jié)構(gòu)【摘要】算法 + 數(shù)據(jù)據(jù)結(jié)構(gòu)=程序。設(shè)計(jì)算算法與選選擇合適適的數(shù)據(jù)據(jù)結(jié)構(gòu)是是程序設(shè)設(shè)計(jì)中相相輔相成成的兩方方面，缺缺一不可可。數(shù)據(jù)據(jù)結(jié)構(gòu)的的選擇一一直是程程序設(shè)計(jì)計(jì)中的重重點(diǎn)、難難點(diǎn)，正正確地應(yīng)應(yīng)用數(shù)據(jù)據(jù)結(jié)構(gòu)，往往能能帶來(lái)意意想不到到的效果果。反之之，如

2、果果忽視了了數(shù)據(jù)結(jié)結(jié)構(gòu)的重重要性，對(duì)某些些問(wèn)題有有時(shí)就得得不到滿滿意的解解答。通通過(guò)對(duì)IIOI998試題題Piccturre的深深入討論論，我們們可以看看到兩種種不同的的數(shù)據(jù)結(jié)結(jié)構(gòu)在解解題中的的應(yīng)用，以及由由此得到到的不同同的算法法效率。本文以以Piccturre問(wèn)題題為例，探討數(shù)數(shù)據(jù)結(jié)構(gòu)構(gòu)的選擇擇對(duì)算法法效率的的影響?！菊摹恳运惴ㄍǔ３Ｊ菦Q定定程序效效率的關(guān)關(guān)鍵，但但一切算算法最終終都要在在相應(yīng)的的數(shù)據(jù)結(jié)結(jié)構(gòu)上實(shí)實(shí)現(xiàn)，許許多算法法的精髓髓就是在在于選擇擇了合適適的數(shù)據(jù)據(jù)結(jié)構(gòu)作作為基礎(chǔ)礎(chǔ)。在程程序設(shè)計(jì)計(jì)中，不不但要注注重算法法設(shè)計(jì)，也要正正確地選選擇數(shù)據(jù)據(jù)結(jié)構(gòu)，這樣往往往能夠夠事半功功倍。

3、在算法時(shí)時(shí)間與空空間效率率的兩方方面，著著重分析析時(shí)間效效率，即即算法的的時(shí)間復(fù)復(fù)雜度，因?yàn)槲椅覀兛偸鞘窍Ｍ坛绦蛟谳^較短的時(shí)時(shí)間內(nèi)給給出我們們所希望望的輸出出。如果果在空間間上過(guò)于于“吝嗇嗇”而使使得時(shí)間間上無(wú)法法承受，對(duì)解題題并無(wú)益益處。本文對(duì)IIOI998的試試題Piictuure作作一些分分析，通通過(guò)兩種種不同數(shù)數(shù)據(jù)結(jié)構(gòu)構(gòu)的選擇擇，將了了解到數(shù)數(shù)據(jù)結(jié)構(gòu)構(gòu)對(duì)算法法本身及及算法效效率的影影響。Pictturee問(wèn)題及及算法設(shè)設(shè)計(jì)Pictturee問(wèn)題Pictturee問(wèn)題是是IOII98的一一道試題題，描述述如下：墻上貼著著一些海海報(bào)、照照片等矩矩形，所所有的邊邊都為垂垂直或水水平。每每個(gè)

4、矩形形可以被被其它矩矩形部分分或完全全遮蓋，所有矩矩形合并并成區(qū)域域的邊界界周長(zhǎng)稱稱為輪廓廓周長(zhǎng)。例如圖11的三個(gè)個(gè)矩形輪輪廓周長(zhǎng)長(zhǎng)為300： 圖1要求編寫寫程序計(jì)計(jì)算輪廓廓周長(zhǎng)。數(shù)據(jù)量限限制：0矩形形數(shù)目 11)的一一般區(qū)間間。一般般情況下下，線段段樹的結(jié)結(jié)點(diǎn)類型型定義如如下： TyypeLinees_TTreee = Objjectt i, j : inttegeer; 結(jié)點(diǎn)表表示的區(qū)區(qū)間的頂頂點(diǎn)標(biāo)號(hào)號(hào)I, J coountt : iinteegerr; 覆蓋這這一結(jié)點(diǎn)點(diǎn)的區(qū)間間數(shù) leeftcchilld, riighttchiild : Linnes_Treee; 二叉叉樹的兩兩個(gè)子結(jié)

5、結(jié)點(diǎn)end關(guān)于Liiness_Trree的的其它數(shù)數(shù)據(jù)域與與定義的的運(yùn)算將將陸續(xù)添添加。圖圖8是一棵棵線段樹樹，描述述的區(qū)間間端點(diǎn)可可以有110種取取值。其其中記錄錄著一個(gè)個(gè)區(qū)間3，6，它它用紅色色的33，5及5，6的并并采表示示。圖中中紅色結(jié)結(jié)點(diǎn)的ccounnt域值值為1，黑色色結(jié)點(diǎn)的的couunt域域值為00。圖8直觀地看看，子結(jié)結(jié)點(diǎn)就是是父結(jié)點(diǎn)點(diǎn)區(qū)間平平均分成成兩部分分。設(shè)LL, RR是父結(jié)結(jié)點(diǎn)的區(qū)區(qū)間端點(diǎn)點(diǎn)，我們們可以增增加Liiness_Trree.Buiild(l, r : inntegger)遞歸地地定義線線段樹如如下:Procceduure Liiness_trree.Buii

6、ld(l, r : inttegeer)I ll 左端點(diǎn)點(diǎn)J rr 右端端點(diǎn)Counnt 00 初始化化If r - l 1 是否否需要生生成子結(jié)結(jié)點(diǎn)，若若r-ll=1則則是初等等區(qū)間 thhen kk (ll + rr) 平均分分為兩部部分 nnew(lefftchhildd) llefttchiild.Buuildd(l, k) 建建立左子子樹 nnew(rigghtcchilld) rrighhtchhildd.Buuildd(k, r) 建立立右子樹樹 ellse llefttchiild nill riighttchiild nill設(shè)根結(jié)點(diǎn)點(diǎn)是Rooot，建樹需需要執(zhí)行行Rooot

7、.BBuilld。由遞歸定定義看出出，線段段樹是一一棵平衡衡樹，高高度為loggN。建立立整棵樹樹需要的的時(shí)間為為O(NN)。以上著重重說(shuō)明了了線段樹樹的存儲(chǔ)儲(chǔ)原理，我們還還應(yīng)建立立線段樹樹的基本本運(yùn)算。線段樹可可以存儲(chǔ)儲(chǔ)多個(gè)區(qū)區(qū)間，所所以支持持區(qū)間插插入運(yùn)算算Linnes_Treee.IInseert(l, r : inntegger)，定義義如下：Procceduure Liiness_Trree.Inssertt(l, r : inntegger) l, rr是待待插入?yún)^(qū)區(qū)間，ll、r都是原原始頂點(diǎn)點(diǎn)坐標(biāo)if (l = aai) andd (aj = rr) thhen coountt

8、coountt + 11 蓋滿整整個(gè)結(jié)點(diǎn)點(diǎn)區(qū)間 ellse iff ll aa(ii + jj) ddiv 2 是否否能覆蓋蓋到右孩孩子結(jié)點(diǎn)點(diǎn)區(qū)間 theen rigghtcchilld.Innserrt(ll, r) 向向右孩子子插入類似地，線段樹樹支持區(qū)區(qū)間的刪刪除Liiness_Trree.Delletee(l, r : iinteegerr)，定定義如下下：Procceduure Liiness_Trree.Delletee(l, r : inntegger) l, rr是待待刪除區(qū)區(qū)間，ll、r都是原原始頂點(diǎn)點(diǎn)坐標(biāo)if (l = aai) andd (aj = rr) thhen c

9、oountt coountt - 11 蓋滿整整個(gè)結(jié)點(diǎn)點(diǎn)區(qū)間 ellse iff ll aa(ii + jj) divv 22 是否否能覆蓋蓋到右孩孩子結(jié)點(diǎn)點(diǎn)區(qū)間 theen rigghtcchilld.Deelette(ll, rr) 向右右孩子刪刪除執(zhí)行Liiness_Trree.Delletee(l, r : iinteegerr) 的先決決條件是是區(qū)間l, r曾曾被插入入且還未未刪除。如果建建樹后插插入?yún)^(qū)間間2，5而刪刪除區(qū)間間3，4是非非法的。通過(guò)分析析插入與與刪除的的路徑，可知LLinees_TTreee.Innserrt與Linnes_Treee.DDeleete的的時(shí)間復(fù)復(fù)雜度

10、均均為O(loggN)。(詳見(jiàn)附錄1)由于線段段樹給每每一個(gè)區(qū)區(qū)間都分分配了結(jié)結(jié)點(diǎn)，利利用線段段樹可以以求區(qū)間間并后的的測(cè)度與與區(qū)間并并后的連連續(xù)段數(shù)數(shù)。測(cè)度由于線段段樹結(jié)構(gòu)構(gòu)遞歸定定義，其其測(cè)度也也可以遞遞歸定義義。增加加數(shù)據(jù)域域Linnes_Treee.MM表示以以該結(jié)點(diǎn)點(diǎn)為根的的子樹的的測(cè)度。M取值如如下： aaj aii 該結(jié)點(diǎn)點(diǎn)Couunt0M = 0 該結(jié)點(diǎn)點(diǎn)為葉結(jié)結(jié)點(diǎn)且CCounnt=00 LLefttchiild.M + RRighhtchhildd.M 該結(jié)點(diǎn)點(diǎn)為內(nèi)部部結(jié)點(diǎn)且且Couunt=0據(jù)此，可可以用LLinees_TTreee.UppDatta來(lái)動(dòng)動(dòng)態(tài)地維維護(hù)Liin

11、ess_Trree.M。UpDDataa在每一一次執(zhí)行行Inssertt或Delletee之后執(zhí)執(zhí)行。定定義如下下：Procceduure Liiness_Trree.UpDDataaif couunt 0 thhen M ajj i 蓋滿區(qū)區(qū)間，測(cè)測(cè)度為aaj aii ellse iff jj - ii = 11 是否否葉結(jié)點(diǎn)點(diǎn) theen M 00 該結(jié)點(diǎn)點(diǎn)是葉結(jié)結(jié)點(diǎn) elsse M LLefttchiild.M + Riighttchiild.M 內(nèi)部結(jié)結(jié)點(diǎn)UpDaata的的復(fù)雜度度為O(1)，則用UUpDaata來(lái)來(lái)動(dòng)態(tài)維維護(hù)測(cè)度度后執(zhí)行行根結(jié)點(diǎn)點(diǎn)的Innserrt與Delletee的

12、復(fù)雜雜度仍為為O(llogNN)。連續(xù)段數(shù)數(shù)這里的連連續(xù)段數(shù)數(shù)指的是是區(qū)間的的并可以以分解為為多少個(gè)個(gè)獨(dú)立的的區(qū)間。如11，22，335，6可以以分解為為兩個(gè)區(qū)區(qū)間11，3與5，6，則則連續(xù)段段數(shù)為22。增加加一個(gè)數(shù)數(shù)據(jù)域LLinees_TTreee.liine表表示該結(jié)結(jié)點(diǎn)的連連續(xù)段數(shù)數(shù)。Liine的的討論比比較復(fù)雜雜，內(nèi)部部結(jié)點(diǎn)不不能簡(jiǎn)單單地將左左右孩子子的Liine相相加。所所以再增增加Liiness_Trree.lbdd與Linnes_Treee.rrbd域域。定義義如下： 11 左端端點(diǎn)I被描述述區(qū)間蓋蓋到lbd = 00 左端點(diǎn)點(diǎn)I不被描描述區(qū)間間蓋到 11 右右端點(diǎn)JJ被描述述區(qū)

13、間蓋蓋到rbd = 00 右端端點(diǎn)J不被描描述區(qū)間間蓋到lbd與與rbdd的實(shí)現(xiàn)現(xiàn)： 1 該結(jié)點(diǎn)點(diǎn)couunt 00lbd = 0 該結(jié)點(diǎn)點(diǎn)是葉結(jié)結(jié)點(diǎn)且ccounnt = 0 lefftchhildd.lbbd 該該結(jié)點(diǎn)是是內(nèi)部結(jié)結(jié)點(diǎn)且CCounnt=00 1 該結(jié)點(diǎn)點(diǎn)couunt 00rbd = 0 該結(jié)點(diǎn)點(diǎn)是葉結(jié)結(jié)點(diǎn)且ccounnt = 0 rigghtcchilld.rbbd 該結(jié)結(jié)點(diǎn)是內(nèi)內(nèi)部結(jié)點(diǎn)點(diǎn)且Coountt=0有了lbbd與rbdd，Linne域就就可以定定義了： 1 該結(jié)結(jié)點(diǎn)coountt 0Linee = 00 該該結(jié)點(diǎn)是是葉結(jié)點(diǎn)點(diǎn)且coountt = 0 Lefftchhi

14、ldd.Liine + Riighttchiild.Liine - 1 當(dāng)該結(jié)結(jié)點(diǎn)是內(nèi)內(nèi)部結(jié)點(diǎn)點(diǎn)且Coountt=0，Lefftchhildd.rbbd = 1且且Rigghtcchilld.lbbd = 1 LLefttchiild.Liine + Riighttchiild.Liine 當(dāng)該該結(jié)點(diǎn)是是內(nèi)部結(jié)結(jié)點(diǎn)且CCounnt=00，Lefftchhildd.rbbd與Rigghtcchilld.lbbd不都都為1據(jù)此，可可以定義義UpDDataa動(dòng)態(tài)態(tài)地維護(hù)護(hù)Linne域。與UppDatta相似似，UppDatta也也在每一一次執(zhí)行行Inssertt或Delletee后執(zhí)行行。定義義如下

15、：Procceduure Liiness_Trree.UpDDataaif couunt 0 是否蓋蓋滿結(jié)點(diǎn)點(diǎn)表示的的區(qū)間 thhen lbbd 1 rbdd 1 Linne 11 ellse iff j - i = 1 是否否為葉結(jié)結(jié)點(diǎn) theen lbdd 00 進(jìn)行行到這一一步，如如果為葉葉結(jié)點(diǎn)， couunt = 00 rbdd 0 linne 00 elsse linne Lefftchhildd.liine + Riighttchiild.liine - LLefttchiild.rbbd * Riighttchiild.lbbd 用乘法法確定LLefttchiild.rbbd與R

16、igghtcchilld.lbbd是否否同時(shí)為為1同時(shí)，由由于增加加了Liine、M等幾個(gè)個(gè)數(shù)據(jù)域域，在建建樹Liiness_Trree.Buiild時(shí)時(shí)要將新新增的域域初始化化。至此，線線段樹構(gòu)構(gòu)造完畢畢，完整整的線段段樹定義義如下：Linees_TTreee = objjectt i, j : inntegger; coountt : inntegger; liine : inntegger; lbbd, rbdd : bbytee; m : iinteegerr; leeftcchilld, riighttchiild : Linnes_treee; prroceedurre Buiil

17、d(l, r : inntegger); prroceedurre Inssertt(l, r : iinteegerr); prroceedurre Delletee(l, r : iinteegerr); prroceedurre UpDDataa; prroceedurre UpDDataa;end有了線段段樹這個(gè)個(gè)工具，可以考考慮利用用樹形結(jié)結(jié)構(gòu)來(lái)描描述一組組超元線線段的狀狀態(tài)。Pictturee問(wèn)題的的數(shù)據(jù)結(jié)結(jié)構(gòu)選擇擇之二：樹形結(jié)結(jié)構(gòu)采用線性性結(jié)構(gòu)描描述一組組超元線線段的狀狀態(tài)并不不能帶來(lái)來(lái)太高的的效率，其中主主要原因因是各組組超元線線段聯(lián)系系不緊。如圖99所示，超元線線段CDD與E

18、F被矩矩形AGGHB遮遮蓋，不不屬于輪輪廓；而而與之相相鄰DDD與FF則“擺擺脫”了了矩形的的遮蓋，屬于輪輪廓的一一部分。 圖9 圖圖10由此類推推，可以以看出相相鄰的超超元線段段組都有有類似的的問(wèn)題。如圖99，DD與FF不被遮遮蓋，可可以這樣樣分析：從左往往右，CCD、EF首先先被遮蓋蓋，但隨隨著BFF的出現(xiàn)現(xiàn)，對(duì)DDD、FF的遮蓋蓋自然消消失。這這一點(diǎn)，正是相相鄰超元元線段組組的內(nèi)在在聯(lián)系。用線性性結(jié)構(gòu)無(wú)無(wú)法表示示出這一一聯(lián)系，因?yàn)楦鞲鹘M的累累計(jì)掃描描過(guò)程是是獨(dú)立的的?，F(xiàn)在在我們用用樹形結(jié)結(jié)構(gòu)來(lái)表表示將較較好地解解決這一一問(wèn)題，因?yàn)榫€線段樹支支持插入入與刪除除及動(dòng)態(tài)態(tài)維護(hù)，可以有有機(jī)聯(lián)系系

19、各組超超元線段段的狀態(tài)態(tài)。我們們把“從從左往右右”當(dāng)作作一個(gè)掃掃描的過(guò)過(guò)程，若若將其嚴(yán)嚴(yán)格地描描述，可可以得到到一個(gè)稱稱為線段段掃描的的過(guò)程：設(shè)立掃描描線段LL。L從左往往右掃描描，停留留在每一一超元線線段組上上。如圖圖10所示示。L的狀態(tài)態(tài)用線段段樹來(lái)表表示，每每一條縱縱向的矩矩形邊看看作一個(gè)個(gè)待合并并區(qū)間。線段樹樹的連續(xù)續(xù)段數(shù)*2表示示該組超超元線段段屬于輪輪廓的線線段數(shù)目目。如圖圖10，L的狀態(tài)態(tài)首先是是G,AAE,C，連續(xù)線線段數(shù)是是1，所以以1*22=2是是該組超超元線段段屬于輪輪廓的數(shù)數(shù)目。接接著L進(jìn)一步步掃描，狀態(tài)改改變?yōu)镋,CC, 連續(xù)線線段數(shù)是是1，所以以該組超超元線段段屬于

20、輪輪廓的數(shù)數(shù)目也是是1*22=2。這樣，上文所所說(shuō)的“超元線線段樹”就用線線段樹來(lái)來(lái)實(shí)現(xiàn)。為了統(tǒng)統(tǒng)一起見(jiàn)見(jiàn)，以后后仍稱線線段樹。掃描過(guò)程程中動(dòng)態(tài)態(tài)地維護(hù)護(hù)L的狀態(tài)態(tài)。參看看圖100，L狀態(tài)的的轉(zhuǎn)換是是在線段段樹中刪刪去區(qū)間間H,BB即G,A造造成的。歸納一一下，有有以下結(jié)結(jié)論：L初始化化為空，即線段段樹剛建建好時(shí)的的情形。掃描時(shí)，遇到矩矩形左邊邊，將其其插入（Inssertt）線段段樹。掃描時(shí)，遇到矩矩形右邊邊，將其其從線段段樹中刪刪除（DDeleete）。由于于從左往往右掃描描，事先先插入了了該矩形形的左邊邊，所以以刪除合合法。參看算式式，以上上的線段段掃描過(guò)過(guò)程可以以得到每每一組超超元線段

21、段的Beelonng(ss)，進(jìn)進(jìn)一步得得到整個(gè)個(gè)圖形輪輪廓的橫橫向邊長(zhǎng)長(zhǎng)。同時(shí)時(shí)，線段段掃描過(guò)過(guò)程還可可以在一一次從左左到右的的掃描中中求得圖圖形輪廓廓的縱向向邊長(zhǎng)。還以圖圖10為例例。在掃掃描線狀狀態(tài)改變變之前，L是G,AAE,C；改變狀狀態(tài)之后后，HH,F、D,B就就“露”了出來(lái)來(lái)，成為為輪廓一一部分。G,AAE,C正正是L改變前前后測(cè)度度的差。如果描描述相鄰鄰的掃描描線狀態(tài)態(tài)的線段段樹分別別為Trree11、Treee2，則掃描描過(guò)程中中“露出出”的縱縱向邊長(zhǎng)長(zhǎng)度為|Treee1.M Trree22.M|。在掃描過(guò)過(guò)程中，遇到的的插入或或刪除稱稱為“事事件”，待插入入或刪除除的線段段稱

22、為“事件線線段”。在掃描描之前，應(yīng)將事事件按橫橫坐標(biāo)從從小到大大排序。（詳見(jiàn)見(jiàn)附錄2）通過(guò)以上上分析，得到較較之線性性結(jié)構(gòu)的的累計(jì)掃掃描過(guò)程程改進(jìn)的的線段掃掃描過(guò)程程的算法法：以矩形頂頂點(diǎn)坐標(biāo)標(biāo)切割平平面，實(shí)實(shí)現(xiàn)橫縱縱坐標(biāo)的的離散化化并建立立映射XX_Maap、Y_MMap。事件排序序Roott.Buuildd(1, N*2)Nowmm 0NowLLinee 0Ans 0for II 1 too 事事件的最最大編號(hào)號(hào) doo if I是是插入事事件 theen Rooot.IInseert(Y_MMap.Cooord事件線線段頂點(diǎn)點(diǎn)1， Y_Mapp.Cooordd事件件線段頂頂點(diǎn)2) els

23、se Rooot.DDeleete(Y_MMap.Cooord事件線線段頂點(diǎn)點(diǎn)1， Y_MMap.Cooord事件線線段頂點(diǎn)點(diǎn)2) noowM RRoott.M noowLiine Rooot.LLinee anns anns + lasstLiine * 22 * (X_MappI Y_MMapI-11) anns anss + |nowwM laastMM| laasM nowwM laastLLinee nnowLLinee排序的時(shí)時(shí)間復(fù)雜雜度為OO(NllogNN)。事事件的最最大編號(hào)號(hào)為N*2，插插入或刪刪除的復(fù)復(fù)雜度為為O(llogNN)，所所以整個(gè)個(gè)過(guò)程效效率為OO(NllogN

24、N)。至至此，以以樹形數(shù)數(shù)據(jù)結(jié)構(gòu)構(gòu)為基礎(chǔ)礎(chǔ)的算法法模式確確立，時(shí)時(shí)間效率率是令人人較為滿滿意的。兩種實(shí)現(xiàn)現(xiàn)方法的的比較兩種數(shù)據(jù)據(jù)結(jié)構(gòu)的的不同之之處不僅僅在于它它們本身身的存儲(chǔ)儲(chǔ)差異、定義的的運(yùn)算差差異，還還在于它它們對(duì)算算法時(shí)間間復(fù)雜度度產(chǎn)生的的影響。線性結(jié)結(jié)構(gòu)產(chǎn)生生的復(fù)雜雜度為OO(N2)，而樹形形結(jié)構(gòu)產(chǎn)產(chǎn)生的復(fù)復(fù)雜度為為O(NNloggN)。以下是是一組數(shù)數(shù)據(jù)，將將兩種數(shù)數(shù)據(jù)結(jié)構(gòu)構(gòu)實(shí)現(xiàn)程程序的運(yùn)運(yùn)行時(shí)間間作一個(gè)個(gè)對(duì)比，可以感感性地認(rèn)認(rèn)識(shí)它們們之間的的效率差差異：數(shù)據(jù)實(shí)現(xiàn)一：線性結(jié)結(jié)構(gòu)實(shí)現(xiàn)二：樹形結(jié)結(jié)構(gòu)Dataa_4_1.TTxt1秒以內(nèi)內(nèi)1秒以內(nèi)內(nèi)Dataa_4_2.TTxtDataa_4

25、_3.TTxt30秒左左右Dataa_4_4.TTxtDataa_4_5.TTxt注：以上上程序在在賽揚(yáng)3300/Borrlannd PPasccal下下運(yùn)行。（程序序清單見(jiàn)見(jiàn)程序1線性結(jié)結(jié)構(gòu)及程序2樹形結(jié)結(jié)構(gòu)）Pictturee問(wèn)題的的推廣基于對(duì)PPictturee問(wèn)題特特征的分分析及樹樹形結(jié)構(gòu)構(gòu)的應(yīng)用用，可以以使問(wèn)題題得到推推廣。離散化思思想可以以使頂點(diǎn)點(diǎn)坐標(biāo)由由整數(shù)實(shí)實(shí)數(shù)。在在算法及及數(shù)據(jù)結(jié)結(jié)構(gòu)的選選擇中，我們已已不再使使用數(shù)據(jù)據(jù)類型為為整數(shù)的的特性。所以PPictturee問(wèn)題的的數(shù)據(jù)類類型可以以推廣到到實(shí)型。為了適適應(yīng)這一一變化，要將MMappped.Cooord的的基類型型改為實(shí)實(shí)型，同同時(shí)將LLinees_TTreee.M改改為實(shí)型型，線段段掃描算算法中的的累加器器anss等涉及及到頂點(diǎn)點(diǎn)坐標(biāo)的的類型也也要改為為實(shí)型。更重要的的是，PPictturee問(wèn)題