




下載本文檔
版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領
文檔簡介
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 解題的第一個任務是能夠求出任意兩條線段間的距離??刹捎梅智闆r始時設有標志符,可以辨認出兩條線之間的關序?qū)儆谝幌碌哪囊环N。 (1)兩條線段都是水平的。先固定一條線段,在觀察另一條線段
8、可能出現(xiàn)的情形。的方法求解。開如圖,圖中的黑線是固定的,紅線的位置是變化的。紅線在黑線的上方還是下方并不重要,關鍵在于其相對的左右位置。圖 1 中 距離 = 黑線左側(cè)點到紅線右側(cè)點的距離圖 2 中 距離 = 紅線左側(cè)點到黑線右側(cè)點的距離除圖 1,圖 2 外的情形,兩條線段在 x 坐標上必然有重合的部分,求距離的公式是一樣的。比如圖 3 距離 = fabs(黑線的 y 坐標 紅線的 y 坐標)(2)兩條線段都是豎直的。可同理分析。(3)一條線段是豎直的,另一條線段為水平的??梢允孪日J為判斷一下,用一個代號豎線的。另一個代號橫線。如圖,豎線用黑色表示,橫線用紅色表示。圖 4,5,6 中,紅線均在黑
9、線的左側(cè)。圖 4 距離=黑線左側(cè)點到紅線的下側(cè)點的距離圖 5 距離=黑線左側(cè)點的 x 坐標 紅線的 x 坐標圖 6 距離=黑線左側(cè)點到紅線的上側(cè)點的距離圖 7,8,9 中,紅線均在黑線的右側(cè)。同理可求得。圖 10,圖 11,圖 12 中,紅線的 x 坐標介于黑線兩端的 x 坐標之間。圖 10圖 11圖 12距離=紅線下端的 y 坐標 黑線的 y 坐標距離=0距離=黑線的 y 坐標 紅線上端的 y 坐標如此可求出任意兩條線段間的距離。2 完成此題的總?cè)蝿?。采?Djikstra 算法,將每條線段視為 Djikstra 算法中的一個點,兩點之間的權值表示原來兩條線間的距離。每個點自身的權值表示從初
10、始位置到此線段所需木板的最小長度。首先初始化各個點的權值,起始線所代表的點權值為 0,其余點的權值為各條線到起始線的距離,并標記起始點已被選過。從除起始點外的點中選出一個權值最小的點,標記第 last個點,并此點為已選。逐一從其余未選點選出一個點作為當前點,并求出 last 點到此當前點的距離 betn ,如果Betn last 點本身的權值,則 betn = last 點本身的權值。(betn 表示 從起始線出發(fā),經(jīng)過 last 線,到達 當前線所需木板的最小長度。)在將 betn 與 當前點原來的權值相比較,如果 betn 當前點原來的權值,則修改當前點的權值。如此反復進行,即從未選點中選取一個權值最小的點,記為 last 點,標記為已選點。根據(jù) last 點,修改其余未
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 幼兒教師資格證考試《綜合素質(zhì)》歷年真題及答案解析(2018-2022年)
- 《語文園地二》教學設計-2024-2025學年語文三年級下冊統(tǒng)編版
- 人教版歷史與社會九年級下冊第五單元 冷戰(zhàn)時期的世界第一課《兩極格局的形成》教學設計設計
- 2025至2030年中國馬路隔離圍欄行業(yè)發(fā)展研究報告
- 2025至2030年中國錐燭行業(yè)投資前景及策略咨詢報告003
- 2025至2030年中國銅合金擠壓件行業(yè)發(fā)展研究報告
- 2025至2030年中國管形鏑燈鎮(zhèn)流器行業(yè)發(fā)展研究報告001
- 六年級信息技術上冊 第1課 走進機器人世界教學設計 粵教版
- 普通高中學生成長紀實報告
- 2024-2025版新教材高中化學 第2章 第2節(jié) 第1課時 氯氣教學設計 新人教版必修第一冊
- 7不甘屈辱 奮勇抗爭-圓明園的訴說(教學設計)-部編版道德與法治五年級下冊
- GB/T 20424-2025重有色金屬精礦產(chǎn)品中有害元素的限量規(guī)范
- 2024年黑龍江省水利投資集團招聘筆試真題
- 2025年蘭考三農(nóng)職業(yè)學院高職單招職業(yè)適應性測試歷年(2019-2024年)真題考點試卷含答案解析
- 2025電動自行車集中充電設施第2部分:充換電服務信息交換
- 2025年長沙軌道交通職業(yè)學院單招綜合素質(zhì)考試題庫完美版
- 2025美國急性冠脈綜合征(ACS)患者管理指南解讀課件
- 國家開放大學電大《國際私法》形考任務1-5題庫及答案
- 統(tǒng)編歷史七年級下冊(2024版)第7課-隋唐時期的科技與文化【課件】f
- 血管導管相關感染預防與控制指南課件
- TSG 23-2021 氣瓶安全技術規(guī)程 含2024年第1號修改單
評論
0/150
提交評論