SGOI14之《宇宙导航站》解题报告
   
　　　　　　　　　　　　　　　　　　　　　　　　　福州一中 石宗寅

　　对于第一小题，大家一定都不陌生，在高一的物理书上都见过了。
　　　　　　　　　v＝sqrt((Gm)/(r))

　　但是要特别注意，因为空间站的位置是固定的，而且K星球只能发射同步轨道卫星，也就是说，卫星的轨道只会在Z坐标所代表的平面上，所以只有Z坐标与K星球相同的点才有必要参与计算。你只要从所有与K星Z坐标相同的点中找出与K星距离最小的点，并求出它们之间的距离r进行计算即可。还有一点注意的是，上式m的单位是米，而测试数据中K星的质量的单位是千克！另外，最后的结果需要用比例尺进行换算。

　　解决第二小题，首先，是求出一个凸包。我们得到凸包之后，接着就是求凸包的面积。求凸多边形面积的一个简单方法就是我们顺次把凸包分割成为n-3个三角形，然后计算三角形面积（如用公式s＝sqrt（p（p-a）（p-b）（p-c））其中p＝（a+b+c）/2。这里要特别注意，要求的是实际面积，而经过计算求出的面积的单位是平方单位，所以你要将此结果乘以比例尺的平方才能得到最终结果。

　　第三小题首先要对平面上的点用直线拟合公式求出控制中心的"轨道"的直线解析式：
　　设解析式：y＝ax+b 对平面上所有点有（n为点的个数，联立①②求解）

　　

　　

　　由此已知X坐标，可用解析式求出Y轴坐标。

　　然后就是判断一个点是否在多边形内，只要从这个点向多边形外做一条射线（随机取极远处的一个点，以这两点为端点做一条线段即可），如果射线不经过多边形顶点，不和多边形边重合（随机取点出现这种情况的概率极小，可以不予考虑，或者发现问题马上重新取点），那么统计射线和多边形的边的交点个数，如果是交点是奇数个表明点在多边形内，否则在多边形外。

　　

　　第四小题就是求最短路径，注意，因为题目中最大测试规模为5000个点，所以不能用邻接矩阵来记录权值，只能用邻接表。计算三维空间内两点距离的公式是：
　　

　　然后就是引用单源最短路DIJKSTRA算法计算了。

　　单源最短路：设置一个顶点集合S并不断地作贪心选择来扩大这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。DIJKSTRA算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist做必要的修改。一旦S包含了所有V中的顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。


    

 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有