国家集训队作业武森subway pla解题报告

1、IOI2009homeworkbyWuSenfromNo.2MiddleschoolofShijiazhuangSubway planning 解题报告河北省石家庄二中武森【题目大意】有 N 城市(每个城市用坐标(xi, yi) 表现在有一个，这个示)，城市中有一个城市是首都，现在要在这个建造铁路，要求这些铁路必须从首都出发，并且必须是笔直的，不能拐弯。为了方便的日常出行，每个到离最近的铁路不能超过距离D，但是的财力有限，又不能建设太多的铁路，现在这个想让你帮忙算算最少要建造多少铁路使得每个城市的居民到达距离最近的铁路的距离不超过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条铁路即可。【思路】通过读题我们对这道题目已经有了初步的了解，根据题目中的信息，我们发现就离城市最近的铁路只要距离不超过D即可，这样就是说铁路经过的地方是一个范围而不是一个点，那么

3、这样，我们不妨以每个城市为中心，以距离D为半径画圆。2IOI2009homeworkbyWuSenfromNo.2MiddleschoolofShijiazhuang那么只要有一条铁路与这个圆相切或相交就满足题目的要求。这样每个城市要求铁路结果的范围，就可以很简单就算出来。3IOI2009homeworkbyWuSenfromNo.2MiddleschoolofShijiazhuang从原点出发，做各个圆的两条切线，如上图（两条颜色线相同的为同一个圆的切线），那么铁路经过的范围就是两条相同颜色线的夹角（小于180° ）部分。现在这道题目就变成了给定二维坐标中的一些线段，想用最少的线段

4、（从原点出发）使得与全部线段相交。那么怎么计算上面那个问题呢？首先，我们可以证明铁路建造在圆的切线上必定最优，因为如果铁路建在不是圆的切线上那么把铁路往切线方向旋转一个角度q，如果不经过切线，则解劣于当前解，这样我们不断往切线方向旋转 ，直至到切线位置。4IOI2009homeworkbyWuSenfromNo.2MiddleschoolofShijiazhuang由于这个问题是在一个环上进行，为了简化问题我们不妨先看看对于线性问题怎么处理？首先，我们要把这些线段进行排序（按照线段的第二个点进行升序排列），使其变得有序，容易处理。然后，我们就有了一个贪心的策略：选取第一条线段的后面一个节点，建

5、造一条铁路。向后遍历所有的线段，直至找到一条线段的第一个点比最新建造的铁路位置靠后，调至，否则调至。将这条线段记为第一条线段调至。结束，跳出。这个贪心的策略的正确性很好证明（可以通过上面的证明来推到），在这里不再赘述。对于现行的问题我们解决了，那么环的问题怎么办呢？首先，我们要按这些线段的两个端点的后一个点的极角为关键字，进行升序排序。我们只需在贪心的策略时候加一维，枚举起始点即可 。这样，我们的做法的时间复杂度为O(n2 ) ，对于题目中的数据范围完全可以应付。这样，我们就比较完美的解决了这道题目。【细节】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