计算几何专题优秀课件.ppt

《计算几何专题优秀课件.ppt》由会员分享，可在线阅读，更多相关《计算几何专题优秀课件.ppt（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算几何专题第1页，本讲稿共63页提纲n n计算几何简介n n计算几何的基本算法n n常见的题型和例题n n计算几何小技巧n n在比赛如何处理计算几何题第2页，本讲稿共63页计算几何简介n n顾名思义，就是需要计算的几何_n n主要任务是计算，和几何证明的关系不大n n讨论点、线、面之间的相互关系，比如线段之间的相交关系，多边形的面积等n n做计算几何题是一项艰苦的体力劳动！第3页，本讲稿共63页计算几何简介n n公认的三种麻烦题之一（模拟，格式，计算几何！）n n亲自动手编写代码是练习计算几何的不二法门！n n通过练习计算几何题，可以使脑筋清醒，coding流利，细化思维，加强查错能力，不再

2、畏惧代码！第4页，本讲稿共63页计算几何的特点n n计算几何本身的算法难度不大，很少有几何意义上计算几何本身的算法难度不大，很少有几何意义上的算法，常作为辅助考察的内容出现。少数题目的算法，常作为辅助考察的内容出现。少数题目（如立体几何）等需要较好的空间想象能力。（如立体几何）等需要较好的空间想象能力。n n做计算的部分非常多，且一般都很复杂，编程的复做计算的部分非常多，且一般都很复杂，编程的复杂度和代码量较大。杂度和代码量较大。n n做计算几何最重要的是细心谨慎，尽可能完整地考虑做计算几何最重要的是细心谨慎，尽可能完整地考虑所有的情况，保证在编写程序的过程中不出错。所有的情况，保证在编写程序

3、的过程中不出错。n n典型的典型的“说的比做的容易得多得多说的比做的容易得多得多”第5页，本讲稿共63页计算几何的基本算法n n图形相交的判定以及求交点n n点与图形的内外关系n n凸包算法第6页，本讲稿共63页线段相交n n计算几何算法中的基本的基本n n高中方法，解方程？n n普适地判断两线段相交？n n恶心情况：规范相交与非规范相交n n定比分点求交点n n多边形的相交n n三维情况第7页，本讲稿共63页点在形内的判定n n凸多边形，可以参考叉积n n凹多边形怎么办？n n可以用射线法n n恶心情况：射线与边相交n n三维情况第8页，本讲稿共63页凸包算法n n何谓凸包？n n凸包的作用

4、：降低平均/最坏情况时间复杂度n n卷包裹法n n恶心情况：三点共线n nGraham算法和Melkman算法n n极角序和水平序第9页，本讲稿共63页计算几何常见题型n n以计算几何为主要考察点的：纯计算几何 几何模拟题n n通过计算几何提升代码量的：枚举几何题 向量几何题 数值几何题第10页，本讲稿共63页纯计算几何n n纯计算几何一般出现的形式是空间几何题。n n提问的方式简单易懂，算法的设计也基本上一目了然。n n需要良好的空间想象能力和计算功底。第11页，本讲稿共63页纯计算几何的例题n n经典问题：骰子上的蚂蚁n n题目大意：在一个立方体的表面上有两只蚂蚁A和B，现在蚂蚁A要沿着立

5、方体的表面爬到蚂蚁B那里去，问蚂蚁A最少需要爬的长度是多少？n n思考：怎样的爬行路线才是合理的？第12页，本讲稿共63页骰子上的蚂蚁n n算法的核心是两点之间线段最短高中数学常识n n如何用线段来表示行走的方案？n n答案是“展开”！n n思考：展开的情况究竟有多少种？第13页，本讲稿共63页骰子上的蚂蚁n n分情况讨论！根据两点连线经过的面的个数，构造不同的平面展开形式n n经过1个面？n n经过2个面？n n经过3个面？n n经过的面越少越好？n n经过4个面？第14页，本讲稿共63页骰子上的蚂蚁n n根据以上的描述，只要我们每次枚举其中一类情况展开，然后计算展开之后平面上两点的距离并取

6、极值即可。n n说得容易做起来费神n n如何描述展开之后点在平面上的坐标？n n向量旋转第15页，本讲稿共63页类似的题目n n比较容易想象的求球面距离（Poj 2354 Titanic)Ural Collegiate Programming Contest 1999n n很难想象的八面体（World Final 2009）第16页，本讲稿共63页几何模拟题n n几何模拟题，顾名思义就是以计算为主要难点，通过几何模拟题，顾名思义就是以计算为主要难点，通过给定的规则进行模拟或者判断，从而回答题目提出的给定的规则进行模拟或者判断，从而回答题目提出的问题。比如说，模拟物体的相对运动，相互碰撞等。问题

7、。比如说，模拟物体的相对运动，相互碰撞等。n n模拟的时候一定要注意分情况讨论所有分支。模拟的时候一定要注意分情况讨论所有分支。n n一般来说，只要完成模拟的过程就能够一般来说，只要完成模拟的过程就能够ACAC，但是要，但是要注意数据中可能存在一些不容易注意到的注意数据中可能存在一些不容易注意到的trickstricks。第17页，本讲稿共63页几何模拟题的例题n n比较典型的例子是和物体运动相关的题目。n nPOJ 3433 Road accident(Northeastern Europe 2005,Far-eastern Subregion)第18页，本讲稿共63页Road accide

8、ntn n题目大意：有两辆车子行驶在路上。现在已知初始时车辆左前方和左后方的坐标，车子的宽度，车子行进的方向以及速度。车子被看作是矩形，并根据位置划分为4个区域。求两车撞击的时候到底是哪两个区域相撞？同时相撞时取编号小的。n n思考：车子怎样才算相撞？车子相撞的状态究竟有多少种？第19页，本讲稿共63页Road accidentn n通过刚刚的描述，本题的麻烦之处在于模拟两车相撞的过程，在两车都运动的时候，无法直观地计算出相撞的情况。n n经典物理方法：选择“相对参考系”，令一台车子固定不动，再来分析另一台车子的情况。第20页，本讲稿共63页Road accidentn n然后，讨论车子相撞时

9、候的样子。n n点对点？n n点对线？n n线对线？n n依次枚举各种情况下两车相撞的时间，选择其中最小的一个，那就是两车真正相撞的情况。第21页，本讲稿共63页Road accidentn n算出啥时候撞的还没完n n同时出现多个撞击点的情况需要进行分析n n注意精度！第22页，本讲稿共63页重点内容相似的题目n nPOJ 3521 Geometry map第23页，本讲稿共63页枚举几何题n n枚举几何题和几何模拟题的界限不是很明显。因为几何类枚举几何题和几何模拟题的界限不是很明显。因为几何类型题目很难逃脱枚举的框架，并且枚举几何题也要求有一型题目很难逃脱枚举的框架，并且枚举几何题也要求有

10、一些模拟的过程。些模拟的过程。n n不过两者侧重不同，模拟类题目的难点在于细节上的考不过两者侧重不同，模拟类题目的难点在于细节上的考察，容易察，容易“差之毫厘失之千里差之毫厘失之千里”，而枚举类几何题一，而枚举类几何题一般是要求完整性，只要枚举到题目要求的所有的可能般是要求完整性，只要枚举到题目要求的所有的可能性就行。性就行。n n一般来说，枚举几何题的规模都是克意限制好的，一般来说，枚举几何题的规模都是克意限制好的，数据范围很小（或者需要一些简单的优化来减少枚数据范围很小（或者需要一些简单的优化来减少枚举的范围）。举的范围）。第24页，本讲稿共63页枚举几何题的例题n n比较典型的例子是和镜

11、面反射相关的题目。n nPOJ 2972 Laser-ball(Northeastern Europe 2004,Western Subregion)第25页，本讲稿共63页Laser-balln n题目大意：在平面上有题目大意：在平面上有N(=100)N(=100)块镜子，镜子看作是块镜子，镜子看作是线段，双面反光，镜子之间互不相交。激光威力有限，至线段，双面反光，镜子之间互不相交。激光威力有限，至多反射多反射K(=10)K(=10)次，允许在同一面镜子上反射多次，并次，允许在同一面镜子上反射多次，并且保证且保证NK=1e6NK=1e6。激光可以贴着镜子传播，并且在。激光可以贴着镜子传播，并

12、且在激光与目标点误差小于激光与目标点误差小于1e-41e-4的时候认为是击中。激光的时候认为是击中。激光从从(0,0)(0,0)发射，问是否能够击中发射，问是否能够击中(X,Y)(X,Y)点？如果可以，点？如果可以，给出一种方案。给出一种方案。n n思考：反射到底表示什么？思考：反射到底表示什么？NKNK的值又有什么意义的值又有什么意义？第26页，本讲稿共63页Laser-balln n题目只要求求出一种方案，因此我们从镜面反射的物理意义来处理这道题。n n很明显，题目意思中的NK=1e6就是枚举的一个提示，而且镜子可以多次反射，降低了很多需要处理的繁杂情况。第27页，本讲稿共63页Laser

13、-balln n每多一次镜面反射，对每面镜子相当于多出了一个目标点。因此，多一次镜面反射总目标点的数目就翻了N倍。n n题目限定了NK=1e6，就意味着就算不去除任何重复计算的情况，时间复杂度依然能够承受。第28页，本讲稿共63页Laser-balln n因此，我们列举出所有经过至多因此，我们列举出所有经过至多K K次镜面反射之后目标次镜面反射之后目标点可能存在的位置。点可能存在的位置。n n算出这些就完了吗？算出这些就完了吗？n nNO!NO!必须对这些位置进行验证，能否成功击中目标？必须对这些位置进行验证，能否成功击中目标？n n验证的方法则是模拟验证的方法则是模拟第29页，本讲稿共63页

14、枚举几何题外一篇n n这种枚举几何题常以离散化扫描线的形式出现。这种枚举几何题常以离散化扫描线的形式出现。n n离散化的方法可以使得枚举成为可能！离散化的方法可以使得枚举成为可能！n n注重分段处理，段与段之间的情况不同，在每一段注重分段处理，段与段之间的情况不同，在每一段之间进行一些处理，然后合并所有的结果。之间进行一些处理，然后合并所有的结果。n n一般出现的问题形式是求极值。一般出现的问题形式是求极值。第30页，本讲稿共63页枚举几何题例题二n nPOJ 3011 Secrets in shadows(Japan 2006 Domestic)第31页，本讲稿共63页Secrets in

15、shadowsn n题目大意：在二维平面上给出一些圆，圆的半径是一定的。现在有一束平行光从无穷远处射入，照射在圆盘上产生长条状的阴影。假设平行光入射的角度可以从0到Pi范围内任意选择，求阴影总宽度的最大/最小值。n n思考：阴影的宽度如何变化？应该怎样进行分段？第32页，本讲稿共63页Secrets in shadowsn n核心问题：阴影的总宽度究竟和什么相关？n n考察在阴影偏转的过程中产生的变化。n n重叠阴影的多少决定了最终总宽度的不同。n n通过分段的方式将阴影重叠状态不变的情况分开讨论。第33页，本讲稿共63页Secrets in shadowsn n在投影边界相互位置一定的情况下

16、，投影的总宽度在该区间内是一个单峰函数！n n证明略n n因此可以采用解方程的方式来解出极值点，分段求出极值点之后合并所有的解，取极大/极小值即可解决本题。第34页，本讲稿共63页类似的题目n nPOJ3703 Intuition of Escape(POJ monthly 2008.10.05)第35页，本讲稿共63页向量几何题n n向量计算是计算几何中非常重要的部分n n向量计算也是计算机程序最能够接受的一种几何计算方式n n向量计算可以和多种问题挂钩。其中典型的一种是半平面求交。第36页，本讲稿共63页半平面求交n n简单例题：POJ 3335 Rotating scoreboard（T

17、ehran 2006 Preliminary）n n题目大意：给出一个多边形，问形内是否存在一个点使得在多边形边界上的任何一点都可以直接看到它。n n思考：怎样的点才能被所有的边都看到？第37页，本讲稿共63页半平面求交n n本质问题：多边形是否有核？n n如何求多边形的核？n n半平面求交的主要难点并不是程序的实现，而是模型的建立n n很多题目并不是非常直观的“半平面求交”的计算几何题。第38页，本讲稿共63页隐藏的半平面求交n n经典问题：鸡尾酒经典问题：鸡尾酒n n题目大意：有若干种鸡尾酒，每一种都含有不同比题目大意：有若干种鸡尾酒，每一种都含有不同比例的三种化学成分。现在有一位客人要求

18、调配一种例的三种化学成分。现在有一位客人要求调配一种新鸡尾酒，可以使用任何任何已有的鸡尾酒作为原新鸡尾酒，可以使用任何任何已有的鸡尾酒作为原料，且混合方式随意。问能否满足客人的要求？料，且混合方式随意。问能否满足客人的要求？n n思考：调配鸡尾酒的本质和计算几何之间的关系思考：调配鸡尾酒的本质和计算几何之间的关系第39页，本讲稿共63页隐藏的半平面求交n n证明以及推导n n类似的题目：UVA 4355-Experiment on a.“Cable”（2009 ACM/ICPC Regional Hangzhou）第40页，本讲稿共63页数值几何题n n问题的答案是一个数值，但是不同于枚举型的

19、几何题，很难找到可以分段的段落点n n常见的形式是二分法+求极值，一般会配合一些几何上的变换n n可以说是最像计算机做的几何题第41页，本讲稿共63页数值几何题例题n nPOJ 3502 Flight Safety(Northwestern Europe 2007)n n题目大意：给定了若干多边形大陆和一条折线段航线，问在航线上距离陆地最远的点距离陆地的距离。第42页，本讲稿共63页Flight safetyn n思考：距离大陆最远的点有什么特点？如何在能找到这个点？n n不断扩展原来的大陆的边界，那么最后一个被覆盖的点一定是距离大陆最远的点n n二分扩展的大小，然后模拟扩展的结果，检验覆盖的

20、结果。第43页，本讲稿共63页计算几何小技巧（1）n nPoj2069 Super star(Japan 2001)n n题目大意：三维空间中给出N(问路-调整方向-沿着该方向走一段-重复问路-到达目的地第48页，本讲稿共63页计算几何技巧（）n nUva 4395 Crop circlesn n来自于33th ACM/ICPC Asia Chengdun n是一道结合了计算几何与数据结构麻烦题第49页，本讲稿共63页计算几何技巧（）n n题目大意：二维平面上有若干(=50000)个圆，圆和圆的互相关系只有两种：相离或者包含。两个圆之间的距离被定义为从一个圆的圆心出发，到达另一个圆的圆心的曲线

21、所经过的圆的边界的次数的最小值。每个圆有一个固定的分值，现在要求找出距离不超过K的一对圆，并且他们之间的差的绝对值尽可能大。第50页，本讲稿共63页计算几何技巧（）n n先撇开计算几何的部分不谈n n因为圆与圆之间只能是包含或者相离，也就是整个圆与圆的关系可以看作一棵树。n n假设我们已经知道了圆与圆之间的这棵相互关系树长得是什么样子，那么我们就可以轻松地求出距离不超过K的两点权值差的最大值，这就是一个数据结构类型的题目。第51页，本讲稿共63页计算几何技巧（）n n现在，问题重新回到了计算几何的部分。n n如何才能够构建出这样一棵能够表示圆和圆之间相互关系的树呢？n n直接用O(N2)的方法

22、毫无疑问会超时。n n因此，我们需要降低算法的复杂度。第52页，本讲稿共63页计算几何技巧（）n n对于给定的图，它有一个很适合利用的特点：树的结构可以通过一条扫描线的切割来完成。n n由于圆与圆之间不相交，因此可以通过简单地枚举当前圆和其切割线上的相邻圆之间的关系来判断。n n这样可以将构树的时间复杂度降低很多。第53页，本讲稿共63页计算几何技巧（）n n但是这样的构图仍然有很严重的问题：我们可以构造一组非常简单的数据使得程序的运行情况达到最坏。n n因此，我们需要对原图进行一次振荡，这样就基本不可能遇到一条扫描线会产生出最坏情况。n n至此，构树的部分就被很好地解决了。第54页，本讲稿共

23、63页总结n n模版的重要性n n比赛中如何处理计算几何题？n n计算几何题容易犯的错误n n怎样训练计算几何题？第55页，本讲稿共63页模版的重要性n n计算几何的恶心程度难以估计n n计算几何的代码量大得很n n因此，计算几何题的模版是至关重要的第56页，本讲稿共63页模版的重要性n n一个好的模版，可以n n大大减少coding的难度，提高编程的速度(比较一下写作业的情况，抄写的总是比较快)n n大大减少犯错误的可能性(模版的正确性是必须保证的)n n让你有更多的精力在大框架上思考n n让你有更多的机会摆脱Tricks的纠缠第57页，本讲稿共63页比赛中如何处理计算几何题？n n计算几何

24、题的虽然麻烦，但是难易度几乎是可以一眼看出计算几何题的虽然麻烦，但是难易度几乎是可以一眼看出来的。来的。n n如果是不会做的计算几何（比如无法抽象出模型，或者如果是不会做的计算几何（比如无法抽象出模型，或者空间感不太好），一般放弃是最好的选择，因为吃力不空间感不太好），一般放弃是最好的选择，因为吃力不讨好讨好-_-_-n n如果是会做的题，那么几分钟之内就可以罗列好解如果是会做的题，那么几分钟之内就可以罗列好解题的流程，并且想清楚如何去完成。剩下的就只是题的流程，并且想清楚如何去完成。剩下的就只是体力活了。体力活了。n n所以，用最快的速度估计题目的难度，并且预算好完成所以，用最快的速度估计题

25、目的难度，并且预算好完成的时间，是在比赛场上应对计算几何题的关键的时间，是在比赛场上应对计算几何题的关键第58页，本讲稿共63页计算几何题容易犯的错误n n探花：中Tricksn n一般来说，计算几何题的题面都会有图，所以读题不容易错。但是图也往往会有误导性，会使我们的思维不全面，容易忽略一些东西。n n因此，在审题的时候千万要注意完整地思考，不要因为有图就跳过题目中的重要条件（虽然我常常这么做-_-)第59页，本讲稿共63页计算几何题容易犯的错误n n榜眼：修改模版时改错n n模版虽然牛，但是模版只能处理大概的情况，很多题目对应的解题方法中模版需要视情况改变。很多时候原本正确的模版，在修改之

26、后就出现了这样那样的问题。n n千万不要想当然，修改也是做题的一部分，一定要认真对待。第60页，本讲稿共63页计算几何题容易犯的错误n n状元！敲错变量n n计算几何的代码量动辙上百行，而且抄写占了很大一部分，查起来相当不容易。很多时候一碗汤就是坏在一个i打成j的地方的。n n写代码虽然要快，但是不出错才是最重要的，次罚时的AC也是AC，只有能AC了才需要考虑罚时！第61页，本讲稿共63页怎样训练计算几何题？n n多做题，多写代码，不要怕麻烦n n多读别人的代码（挑风格好的读，不要学Topcoder），掌握快速发现问题的能力和大方向上的思考能力n n认真准备模版，确保自己有足够的能力应付可能出现的修改。n n培养良好的空间感觉n n第62页，本讲稿共63页Thats allThank you!第63页，本讲稿共63页