教程分析案例1292will indiana jones get there

1、解題：Willna Jones Get There?題目來源：http解法或類型：Djikstra作者：/JudgeOnline/showproblem?problem_id=1292Willna Jones Get There?TimeLimit:1SMemory Limit:1000KTotal Submit:58 Accepted:25Descriptionna Jones is in a deserted city, annihilated during a war. Roofs of all houses have been destroyed and only portions o

2、f walls are still standing. The ground is so full ofminest the only safe way to move around the city is walkiner the remainingwalls. The misof our hero is to saverson who is trappedhe city. In orderto move betn two walls which are not connectedna Jones thought of taking n the two walls and then cros

3、swith him a wooden board which he could place bet from one to the other.Initialitions ofna Jones and the trappedare both on some section ofthe walls.Besides, walls are eitherhe direction South-North or West-East.You will be given a map of the city remains. Your misis to determine theminimum length o

4、f the wooden boardna Jones needs to carry in order to get tothe trapped.InputYour program should pros several test cases. Each test case starts winegerN indicating the number of wall sections remaininghe city (2 = N = 1000).Each of the next N lines describes a wall section. Thewall section to appear

5、 isthe section wherena Jones stands at the beginning.The second section to appearis the section where the trappedstands. Each wall section description consistsof threeegers X,Y and L (-10000 = X ,Y ,L = 0,the section is West-East, with length L; if L 0,the section is North-South, with length |L|.of

6、input is indicated by N = 0.OutputFor each test casehe input your program should produce one line of output,containing a real value representing the length of the wooden boardna Jonesmust carry. The length must be pred as a real number with two-digit preci, andthe last decimal digit must be rounded.

7、 The input will not contaest cases wheredifferenin rounding are significant.SampleInput141675222401346631823533378676652-2322-2-212-221-2-10 0 20-5 1 1050 50 1000Sample Output1.411.00SourceSoumerica 2002解題思路：1 解題的第一個任務(wù)是能夠求出任意兩條線段間的距離。可采用分情況始時設(shè)有標(biāo)志符，可以辨認(rèn)出兩條線之間的關(guān)序?qū)儆谝幌碌哪囊环N。 (1)兩條線段都是水平的。先固定一條線段，在觀察另一條線段

8、可能出現(xiàn)的情形。的方法求解。開如圖，圖中的黑線是固定的，紅線的位置是變化的。紅線在黑線的上方還是下方并不重要，關(guān)鍵在于其相對的左右位置。圖 1 中 距離 = 黑線左側(cè)點到紅線右側(cè)點的距離圖 2 中 距離 = 紅線左側(cè)點到黑線右側(cè)點的距離除圖 1，圖 2 外的情形，兩條線段在 x 坐標(biāo)上必然有重合的部分，求距離的公式是一樣的。比如圖 3 距離 = fabs（黑線的 y 坐標(biāo) 紅線的 y 坐標(biāo)）(2)兩條線段都是豎直的?？赏矸治?。(3)一條線段是豎直的，另一條線段為水平的?？梢允孪日J(rèn)為判斷一下，用一個代號豎線的。另一個代號橫線。如圖，豎線用黑色表示，橫線用紅色表示。圖 4，5，6 中，紅線均在黑

9、線的左側(cè)。圖 4 距離=黑線左側(cè)點到紅線的下側(cè)點的距離圖 5 距離=黑線左側(cè)點的 x 坐標(biāo) 紅線的 x 坐標(biāo)圖 6 距離=黑線左側(cè)點到紅線的上側(cè)點的距離圖 7，8，9 中，紅線均在黑線的右側(cè)。同理可求得。圖 10，圖 11，圖 12 中，紅線的 x 坐標(biāo)介于黑線兩端的 x 坐標(biāo)之間。圖 10圖 11圖 12距離=紅線下端的 y 坐標(biāo) 黑線的 y 坐標(biāo)距離=0距離=黑線的 y 坐標(biāo) 紅線上端的 y 坐標(biāo)如此可求出任意兩條線段間的距離。2 完成此題的總?cè)蝿?wù)。采用 Djikstra 算法，將每條線段視為 Djikstra 算法中的一個點，兩點之間的權(quán)值表示原來兩條線間的距離。每個點自身的權(quán)值表示從初

10、始位置到此線段所需木板的最小長度。首先初始化各個點的權(quán)值，起始線所代表的點權(quán)值為 0，其余點的權(quán)值為各條線到起始線的距離，并標(biāo)記起始點已被選過。從除起始點外的點中選出一個權(quán)值最小的點，標(biāo)記第 last個點，并此點為已選。逐一從其余未選點選出一個點作為當(dāng)前點，并求出 last 點到此當(dāng)前點的距離 betn ，如果Betn last 點本身的權(quán)值，則 betn = last 點本身的權(quán)值。（betn 表示 從起始線出發(fā)，經(jīng)過 last 線，到達(dá) 當(dāng)前線所需木板的最小長度。）在將 betn 與 當(dāng)前點原來的權(quán)值相比較，如果 betn 當(dāng)前點原來的權(quán)值,則修改當(dāng)前點的權(quán)值。如此反復(fù)進(jìn)行，即從未選點中選取一個權(quán)值最小的點，記為 last 點，標(biāo)記為已選點。根據(jù) last 點，修改其余未