


版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、IOI2009homeworkbyWuSenfromNo.2MiddleschoolofShijiazhuangSubway planning 解題報告河北省石家莊二中武森【題目大意】有 N 城市(每個城市用坐標(xi, yi) 表現(xiàn)在有一個,這個示),城市中有一個城市是首都,現(xiàn)在要在這個建造鐵路,要求這些鐵路必須從首都出發(fā),并且必須是筆直的,不能拐彎。為了方便的日常出行,每個到離最近的鐵路不能超過距離D,但是的財力有限,又不能建設太多的鐵路,現(xiàn)在這個想讓你幫忙算算最少要建造多少鐵路使得每個城市的居民到達距離最近的鐵路的距離不超過D?數據范圍: (1 £ N £ 500,0
2、 £ D£ 150,-100 £ xi £ 100,-100 £ yi £ 100)舉例:城市坐標:(7,1), (-1,-4), (-3,1), (-3,-1), (2,3), (2,4), (2,-2), (6,-2)如下圖:1IOI2009homeworkbyWuSenfromNo.2MiddleschoolofShijiazhuang最終只需要建造4條鐵路即可?!舅悸贰客ㄟ^讀題我們對這道題目已經有了初步的了解,根據題目中的信息,我們發(fā)現(xiàn)就離城市最近的鐵路只要距離不超過D即可,這樣就是說鐵路經過的地方是一個范圍而不是一個點,那么
3、這樣,我們不妨以每個城市為中心,以距離D為半徑畫圓。2IOI2009homeworkbyWuSenfromNo.2MiddleschoolofShijiazhuang那么只要有一條鐵路與這個圓相切或相交就滿足題目的要求。這樣每個城市要求鐵路結果的范圍,就可以很簡單就算出來。3IOI2009homeworkbyWuSenfromNo.2MiddleschoolofShijiazhuang從原點出發(fā),做各個圓的兩條切線,如上圖(兩條顏色線相同的為同一個圓的切線),那么鐵路經過的范圍就是兩條相同顏色線的夾角(小于180° )部分。現(xiàn)在這道題目就變成了給定二維坐標中的一些線段,想用最少的線段
4、(從原點出發(fā))使得與全部線段相交。那么怎么計算上面那個問題呢?首先,我們可以證明鐵路建造在圓的切線上必定最優(yōu),因為如果鐵路建在不是圓的切線上那么把鐵路往切線方向旋轉一個角度q,如果不經過切線,則解劣于當前解,這樣我們不斷往切線方向旋轉 ,直至到切線位置。4IOI2009homeworkbyWuSenfromNo.2MiddleschoolofShijiazhuang由于這個問題是在一個環(huán)上進行,為了簡化問題我們不妨先看看對于線性問題怎么處理?首先,我們要把這些線段進行排序(按照線段的第二個點進行升序排列),使其變得有序,容易處理。然后,我們就有了一個貪心的策略:選取第一條線段的后面一個節(jié)點,建
5、造一條鐵路。向后遍歷所有的線段,直至找到一條線段的第一個點比最新建造的鐵路位置靠后,調至,否則調至。將這條線段記為第一條線段調至。結束,跳出。這個貪心的策略的正確性很好證明(可以通過上面的證明來推到),在這里不再贅述。對于現(xiàn)行的問題我們解決了,那么環(huán)的問題怎么辦呢?首先,我們要按這些線段的兩個端點的后一個點的極角為關鍵字,進行升序排序。我們只需在貪心的策略時候加一維,枚舉起始點即可 。這樣,我們的做法的時間復雜度為O(n2 ) ,對于題目中的數據范圍完全可以應付。這樣,我們就比較完美的解決了這道題目?!炯毠?jié)】5IOI2009homeworkbyWuSenfromNo.2Middleschool
6、ofShijiazhuang由于這道題目用到了實數運算,所以我們要考慮進度的誤差。對于那些到首都的距離小于D的城市,我們在進行貪心時,可以不用考慮。對于圓的兩條切線,分別在第一、四象限的情況,要進行特殊處理。【原題】Subway planningThe government in a foreign country is looking into the possibility ofestablishing a subway system in its capital. Because of practical reasons,they would like each subway line
7、to start at the central station and then goin a straight line in some angle as far as necessary. You have been hired toinvestigate whether such an approach is feasible. Given the coordinates ofimportant places in the city as well as theum distance these placescan be from a subway station (possibly t
8、he central station, which isalready built), your job is to calculate the minimum number of subwaylines needed. You may assume that any number of subway stations can bebuilt along a subway line.6IOI2009homeworkbyWuSenfromNo.2MiddleschoolofShijiazhuangFigure 1: The figure above corresponds to the firs
9、t data set in the exampleinput.InputThe first line in the input file contains an integer N, the number of datasets to follow. Each set starts with two integers, n and d (1 <= n <= 500, 0<= d < 150). n is the number of important places in the city that musthave a subway station nearby, an
10、d d is theum distance allowedbetween an important place and a subway station. Then comes n lines,each line containing two integers x and y (100 <= x, y <= 100), thecoordinates of an important place in the capital. The central station willalways have coordinates 0, 0. All pairs of coordinates within a data setwill be distinct (and none will be 0, 0).7IOI2009homeworkbyWuSenfromNo.2MiddleschoolofShijiazhuangOutputFor each data set, output a single integer on a line by itself: the minimumnumber of subway lines needed to ma
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年非營利組織管理與發(fā)展考試試卷及答案
- 安全環(huán)保主題的演講稿9篇
- 小商品買賣合同(11篇)
- 新興電力系統(tǒng)優(yōu)化與沙盒技術的研究與實踐案例分享
- 吉林白山圖書館招聘試題帶答案分析2024年
- 黑龍江鶴崗圖書館招聘試題帶答案分析2024年
- 廣東珠海圖書館招聘試題帶答案分析2024年
- 北京通州區(qū)圖書館招聘試題帶答案分析2024年
- 保利物業(yè)考試試題及答案
- 2024鄭州黃河護理職業(yè)學院單招《物理》考前沖刺練習題及答案詳解
- 建筑工程施工現(xiàn)場噪聲及其控制技術
- 2023年版工程建設標準強制性條文 水利工程部分
- 2022-2023學年福建省三明市高二(下)期末生物試卷(含解析)
- JBT 14857-2023 氧化鋁焙燒煙氣脫硝裝置 (正式版)
- 大數據技術與智能制造的深度融合
- 醫(yī)院收費價格注意培訓課件
- 23《海底世界》 第二課時 公開課一等獎創(chuàng)新教學設計
- 2024屆黑龍江省哈師大附屬中學物理高二下期末統(tǒng)考試題含解析
- 護士重癥監(jiān)護室護理的進修
- 2024年智能穿戴行業(yè)培訓資料實戰(zhàn)手冊
- 完整英文版質量手冊(e)
評論
0/150
提交評論