集训队作业试题名称_第1页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

试题名称：DrivingDirections试题描述有一外星人的圆状飞船，半径r，需要从出发点A运行到目的地B。与之同时，在地图的其他地方有n个物，每个物都是横平竖直的矩形，大小不一。已知飞船不可以穿过物，但可以与物相切。试求出飞船从A点到B点最短路径的长度（指圆心限制0n所有的物互相之间不相交或者接触思考首先可以把外星人的飞船收缩为一个点与此同时所有的建筑物也向外扩展r的找出最短路径上的“关键点想象一根绷直的绳子被从A点拉到B点，则这根绳子一定满从A点或者B点以切线的方式某一段圆弧以公切线的方式从一段圆弧另一段圆弧围绕着某一个物的外壳行进Dijkstra算法求解最短路径。但是这里面判断一条边是否可行是非常麻烦与繁琐的工作，为了方便起见，下文中所提到的向量同时看作一个复数，即a(x,y)xyi，算法介绍关键点1第一类关键点：起点（终点）CPPQ1PCPQ1PC2r2PCei;PQ2PC2r2PC2第二类关键点：两个圆之间的（外）QC14QC142rC1C2e2CPCPCPr1 2CCe1P3Q3P4Q4只有当两个圆相离的时候才能够得到，假设dC1C2

CPCQrC

ei；CPCQrC

1 2 13

1 2 1物的计算，对于每一个圆角矩形选取红色所示的4个点一起作为关键点：当围绕某一个建筑物走的时候每一段圆弧连接两个关键一段圆弧（90度）4~6（粗实线为待判线段/圆图 图图 图7中这很让人头疼的情况本题中却不会带来麻烦，因为角落上的圆已经把这条线段的可综合以上各种情况，用如下两个步骤判断一条线段（一段圆弧）是否可行线段（弧）线段（弧）现在来总结一下可能出现的边的种类起点（终点）围绕着某一个建筑绕行一周建立的边（可能有圆弧部分起点、终点直接连线效率分析不难看出最多形成O(n2个关键点（圆与圆的公切线）以及O(n2条边（在环绕建筑物的时候一个点只被连一条边Dijkstra过程的复杂度应为O(

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论