國家集訓隊作業(yè)武森subway pla解題報告

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