tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> 初二数学 >>

计算几何专题


计算几何专题
Presented by Mars 20092009-7-13

提纲
计算几何简介 计算几何的基本算法 常见的题型和例题 计算几何小技巧 在比赛如何处理计算几何题

计算几何简介
顾名思义,就是需要计算的几何^_^ 顾名思义,就是需要计算的几何^_^ 主要任务是计算,和几何证明的关系不大 讨论点,线,面之间的相互关系,比如线 段之间的相交关系,多边形的面积等 做计算几何题是一项艰苦的体力劳动!

计算几何简介
公认的三种麻烦题之一(模拟,格式,计 算几何!) 亲自动手编写代码是练习计算几何的不二 法门! 通过练习计算几何题,可以使脑筋清醒, coding流利,细化思维,加强查错能力, coding流利,细化思维,加强查错能力, 不再畏惧代码!

计算几何的特点
计算几何本身的算法难度不大,很少有几何意义 上的算法,常作为辅助考察的内容出现.少数题 目(如立体几何)等需要较好的空间想象能力. 做计算的部分非常多,且一般都很复杂,编程的 复杂度和代码量较大. 做计算几何最重要的是细心谨慎,尽可能完整地 考虑所有的情况,保证在编写程序的过程中不出 错. 典型的"说的比做的容易得多得多" 典型的"说的比做的容易得多得多"……

计算几何的基本算法
图形相交的判定以及求交点 点与图形的内外关系 凸包算法

线段相交
计算几何算法中的基本的基本 高中方法,解方程? 普适地判断两线段相交? 恶心情况:规范相交与非规范相交 定比分点求交点 多边形的相交 三维情况

点在形内的判定
凸多边形,可以参考叉积 凹多边形怎么办? 可以用射线法 恶心情况:射线与边相交 三维情况

凸包算法
何谓凸包? 凸包的作用:降低平均/ 凸包的作用:降低平均/最坏情况时间复杂 度 卷包裹法 恶心情况:三点共线 Graham算法和Melkman算法 Graham算法和Melkman算法 极角序和水平序

计算几何常见题型
以计算几何为主要考察点的: 纯计算几何 几何模拟题 通过计算几何提升代码量的: 枚举几何题 向量几何题 数值几何题

纯计算几何
纯计算几何一般出现的形式是空间几何题. 提问的方式简单易懂,算法的设计也基本 上一目了然. 需要良好的空间想象能力和计算功底.

纯计算几何的例题
经典问题:骰子上的蚂蚁 题目大意:在一个立方体的表面上有两只 蚂蚁A 蚂蚁A和B,现在蚂蚁A要沿着立方体的表 ,现在蚂蚁A 面爬到蚂蚁B那里去,问蚂蚁A 面爬到蚂蚁B那里去,问蚂蚁A最少需要爬 的长度是多少? 思考:怎样的爬行路线才是合理的?

骰子上的蚂蚁
算法的核心是两点之间线段最短——高中 算法的核心是两点之间线段最短——高中 数学常识 如何用线段来表示行走的方案? 答案是"展开" 答案是"展开"! 思考:展开的情况究竟有多少种?

骰子上的蚂蚁
分情况讨论!根据两点连线经过的面的个 数,构造不同的平面展开形式 经过1 经过1个面? 经过2 经过2个面? 经过3 经过3个面? 经过的面越少越好? 经过4 经过4个面?

骰子上的蚂蚁
根据以上的描述,只要我们每次枚举其中 一类情况展开,然后计算展开之后平面上 两点的距离并取极值即可. 说得容易~~做起来费神 说得容易~~做起来费神 如何描述展开之后点在平面上的坐标? 向量旋转

类似的题目
比较容易想象的——求球面距离(Poj 比较容易想象的——求球面距离(Poj 2354 Titanic) Ural Collegiate Programming Contest 1999

很难想象的——八面体(World 很难想象的——八面体(World Final 2009) 2009)

几何模拟题
几何模拟题,顾名思义就是以计算为主要难点, 通过给定的规则进行模拟或者判断,从而回答题 目提出的问题.比如说,模拟物体的相对运动, 相互碰撞等. 模拟的时候一定要注意分情况讨论所有分支. 一般来说,只要完成模拟的过程就能够AC,但是 一般来说,只要完成模拟的过程就能够AC,但是 要注意数据中可能存在一些不容易注意到的 tricks. tricks.

几何模拟题的例题
比较典型的例子是和物体运动相关的题目. POJ 3433 Road accident (Northeastern Europe 2005, FarFareastern Subregion)

Road accident
题目大意:有两辆车子行驶在路上.现在 已知初始时车辆左前方和左后方的坐标, 车子的宽度,车子行进的方向以及速度. 车子被看作是矩形,并根据位置划分为4 车子被看作是矩形,并根据位置划分为4个 区域.求两车撞击的时候到底是哪两个区 域相撞?同时相撞时取编号小的. 思考:车子怎样才算相撞?车子相撞的状 态究竟有多少种?

Road accident
通过刚刚的描述,本题的麻烦之处在于模 拟两车相撞的过程,在两车都运动的时候, 无法直观地计算出相撞的情况. 经典物理方法:选择"相对参考系" 经典物理方法:选择"相对参考系",令 一台车子固定不动,再来分析另一台车子 的情况.

Road accident
然后,讨论车子相撞时候的样子. 点对点? 点对线? 线对线? 依次枚举各种情况下两车相撞的时间,选 择其中最小的一个,那就是两车真正相撞 的情况.

Road accident
算出啥时候撞的还没完…… 算出啥时候撞的还没完…… 同时出现多个撞击点的情况需要进行分析 注意精度!

重点内容相似的题目
POJ 3521 Geometry map

枚举几何题
枚举几何题和几何模拟题的界限不是很明显.因 为几何类型题目很难逃脱枚举的框架,并且枚举 几何题也要求有一些模拟的过程. 不过两者侧重不同,模拟类题目的难点在于细节 上的考察,容易"差之毫厘失之千里" 上的考察,容易"差之毫厘失之千里",而枚举 类几何题一般是要求完整性,只要枚举到题目要 求的所有的可能性就行. 一般来说,枚举几何题的规模都是克意限制好的, 数据范围很小(或者需要一些简单的优化来减少 枚举的范围).

枚举几何题的例题
比较典型的例子是和镜面反射相关的题目. POJ 2972 Laser-ball (Northeastern LaserEurope 2004, Western Subregion)

LaserLaser-ball
题目大意:在平面上有N(<=100)块镜子,镜子 题目大意:在平面上有N(<=100)块镜子,镜子 看作是线段,双面反光,镜子之间互不相交.激 光威力有限,至多反射K(<=10)次,允许在同一 光威力有限,至多反射K(<=10)次,允许在同一 面镜子上反射多次,并且保证N^K<=1e6.激 面镜子上反射多次,并且保证N^K<=1e6.激 光可以贴着镜子传播,并且在激光与目标点误差 小于1e- 的时候认为是击中.激光从(0,0)发射, 小于1e-4的时候认为是击中.激光从(0,0)发射, 问是否能够击中(X,Y)点?如果可以,给出一种方 问是否能够击中(X,Y)点?如果可以,给出一种方 案. 思考:反射到底表示什么?N^K的值又有什么意 思考:反射到底表示什么?N^K的值又有什么意 义?

LaserLaser-ball
题目只要求求出一种方案,因此我们从镜 面反射的物理意义来处理这道题. 很明显,题目意思中的N^K<=1e6就是枚 很明显,题目意思中的N^K<=1e6就是枚 举的一个提示,而且镜子可以多次反射, 降低了很多需要处理的繁杂情况.

LaserLaser-ball
每多一次镜面反射,对每面镜子相当于多 出了一个目标点.因此,多一次镜面反射 总目标点的数目就翻了N 总目标点的数目就翻了N倍. 题目限定了N^K<=1e6,就意味着就算不 题目限定了N^K<=1e6,就意味着就算不 去除任何重复计算的情况,时间复杂度依 然能够承受.

LaserLaser-ball
因此,我们列举出所有经过至多K 因此,我们列举出所有经过至多K次镜面反射之 后目标点可能存在的位置. 算出这些就完了吗? NO!必须对这些位置进行验证,能否成功击中目 NO!必须对这些位置进行验证,能否成功击中目 标? 验证的方法则是模拟…… 验证的方法则是模拟……

枚举几何题外一篇
这种枚举几何题常以离散化扫描线的形式出现. 离散化的方法可以使得枚举成为可能! 注重分段处理,段与段之间的情况不同,在每一 段之间进行一些处理,然后合并所有的结果. 一般出现的问题形式是求极值.

枚举几何题例题二
POJ 3011 Secrets in shadows (Japan 2006 Domestic)

Secrets in shadows
题目大意:在二维平面上给出一些圆,圆 的半径是一定的.现在有一束平行光从无 穷远处射入,照射在圆盘上产生长条状的 阴影.假设平行光入射的角度可以从0 阴影.假设平行光入射的角度可以从0到Pi 范围内任意选择,求阴影总宽度的最大/ 范围内任意选择,求阴影总宽度的最大/最 小值. 思考:阴影的宽度如何变化?应该怎样进 行分段?

Secrets in shadows
核心问题:阴影的总宽度究竟和什么相关? 考察在阴影偏转的过程中产生的变化. 重叠阴影的多少决定了最终总宽度的不同. 通过分段的方式将阴影重叠状态不变的情 况分开讨论.

Secrets in shadows
在投影边界相互位置一定的情况下,投影 的总宽度在该区间内是一个单峰函数! 证明略…… 证明略…… 因此可以采用解方程的方式来解出极值点, 分段求出极值点之后合并所有的解,取极 大/极小值即可解决本题.

类似的题目
POJ3703 Intuition of Escape (POJ monthly 2008.10.05)

向量几何题
向量计算是计算几何中非常重要的部分 向量计算也是计算机程序最能够接受的一 种几何计算方式 向量计算可以和多种问题挂钩.其中典型 的一种是半平面求交.

半平面求交
简单例题:POJ 简单例题:POJ 3335 Rotating scoreboard( scoreboard(Tehran 2006 Preliminary) Preliminary) 题目大意:给出一个多边形,问形内是否 存在一个点使得在多边形边界上的任何一 点都可以直接看到它. 思考:怎样的点才能被所有的边都看到?

半平面求交
本质问题:多边形是否有核? 如何求多边形的核?

半平面求交的主要难点并不是程序的实现, 而是模型的建立 很多题目并不是非常直观的"半平面求交" 很多题目并不是非常直观的"半平面求交" 的计算几何题.

隐藏的半平面求交
经典问题:鸡尾酒 题目大意:有若干种鸡尾酒,每一种都含有不同 比例的三种化学成分.现在有一位客人要求调配 一种新鸡尾酒,可以使用任何任何已有的鸡尾酒 作为原料,且混合方式随意.问能否满足客人的 要求? 思考:调配鸡尾酒的本质和计算几何之间的关系

隐藏的半平面求交
证明以及推导 类似的题目:UVA 类似的题目:UVA 4355 - Experiment on a ... "Cable"(2009 ACM/ICPC Cable" Regional Hangzhou) Hangzhou)

数值几何题
问题的答案是一个数值,但是不同于枚举 型的几何题,很难找到可以分段的段落点 常见的形式是二分法+ 常见的形式是二分法+求极值,一般会配合 一些几何上的变换 可以说是最像计算机做的几何题…… 可以说是最像计算机做的几何题……

数值几何题例题
POJ 3502 Flight Safety (Northwestern Europe 2007) 题目大意:给定了若干多边形大陆和一条 折线段航线,问在航线上距离陆地最远的 点距离陆地的距离.

Flight safety
思考:距离大陆最远的点有什么特点?如 何在能找到这个点? 不断扩展原来的大陆的边界,那么最后一 个被覆盖的点一定是距离大陆最远的点 二分扩展的大小,然后模拟扩展的结果, 检验覆盖的结果.

计算几何小技巧(1 计算几何小技巧(1)
Poj2069 Super star ( Japan 2001 ) 题目大意:三维空间中给出N(<=30)个点, 题目大意:三维空间中给出N(<=30)个点, 要求一个半径最小的球覆盖所有的这些点. 输出该球的半径长度. 思考:如何枚举才能完整地列举出所有可 能的情况?

计算几何小技巧(1 计算几何小技巧(1)
枚举在球的边界上的点的个数 易证至少有两个点位于球的边界上 枚举:两点(直径)/ 枚举:两点(直径)/三点(过球心的平面) /三点(特殊情况三点共线)/四点(四点组 三点(特殊情况三点共线)/ 成球面)/ 成球面)/四点(特殊情况四点共面)

计算几何小技巧(1 计算几何小技巧(1)
每次枚举完成后,根据枚举的结果求出球 心的位置并加以验证 完成枚举后取最小值即可 说来挺轻松,实现的难度如何呢?

计算几何小技巧(1 计算几何小技巧(1)
变步长法——来自于模拟退火算法 变步长法——来自于模拟退火算法 类似人在第一次要去到某个地方时的策略 先沿大方向走,沿途问路 一开始认准方向就行,后来就要求精确到 街巷门牌号了.

计算几何小技巧(1 计算几何小技巧(1)
根据这个,我们可以得出解决本题的简单 方法. 定初始位置- 问路- 调整方向定初始位置->问路->调整方向->沿着该方 向走一段- 重复问路- ......向走一段->重复问路->......->到 达目的地

计算几何技巧(2)
Uva 4395 Crop circles 来自于33th 来自于33th ACM/ICPC Asia Chengdu 是一道结合了计算几何与数据结构麻烦题

计算几何技巧(2)
题目大意:二维平面上有若干(<=50000) 题目大意:二维平面上有若干(<=50000) 个圆,圆和圆的互相关系只有两种:相离 或者包含.两个圆之间的距离被定义为从 一个圆的圆心出发,到达另一个圆的圆心 的曲线所经过的圆的边界的次数的最小值. 每个圆有一个固定的分值,现在要求找出 距离不超过K 距离不超过K的一对圆,并且他们之间的差 的绝对值尽可能大.

计算几何技巧(2)
先撇开计算几何的部分不谈 因为圆与圆之间只能是包含或者相离,也 就是整个圆与圆的关系可以看作一棵树. 假设我们已经知道了圆与圆之间的这棵相 互关系树长得是什么样子,那么我们就可 以轻松地求出距离不超过K 以轻松地求出距离不超过K的两点权值差的 最大值,这就是一个数据结构类型的题目.

计算几何技巧(2)
现在,问题重新回到了计算几何的部分. 如何才能够构建出这样一棵能够表示圆和 圆之间相互关系的树呢? 直接用O(N^2)的方法毫无疑问会超时. 直接用O(N^2)的方法毫无疑问会超时. 因此,我们需要降低算法的复杂度.

计算几何技巧(2)
对于给定的图,它有一个很适合利用的特 点:树的结构可以通过一条扫描线的切割 来完成. 由于圆与圆之间不相交,因此可以通过简 单地枚举当前圆和其切割线上的相邻圆之 间的关系来判断. 这样可以将构树的时间复杂度降低很多.

计算几何技巧(2)
但是这样的构图仍然有很严重的问题:我 们可以构造一组非常简单的数据使得程序 的运行情况达到最坏. 因此,我们需要对原图进行一次振荡,这 样就基本不可能遇到一条扫描线会产生出 最坏情况. 至此,构树的部分就被很好地解决了.

总结
模版的重要性 比赛中如何处理计算几何题? 计算几何题容易犯的错误 怎样训练计算几何题?

模版的重要性
计算几何的恶心程度难以估计 计算几何的代码量大得很 因此,计算几何题的模版是至关重要的

模版的重要性
一个好的模版,可以…… 一个好的模版,可以…… 大大减少coding的难度,提高编程的速度 大大减少coding的难度,提高编程的速度 (比较一下写作业的情况,抄写的总是比较 快) 大大减少犯错误的可能性( 大大减少犯错误的可能性(模版的正确性是 必须保证的) 必须保证的) 让你有更多的精力在大框架上思考 让你有更多的机会摆脱Tricks的纠缠 让你有更多的机会摆脱Tricks的纠缠

比赛中如何处理计算几何题?
计算几何题的虽然麻烦,但是难易度几乎是可以 一眼看出来的. 如果是不会做的计算几何(比如无法抽象出模型, 或者空间感不太好),一般放弃是最好的选择, 因为吃力不讨好因为吃力不讨好-_如果是会做的题,那么几分钟之内就可以罗列好 解题的流程,并且想清楚如何去完成.剩下的就 只是体力活了. 所以,用最快的速度估计题目的难度,并且预算 好完成的时间,是在比赛场上应对计算几何题的 关键

计算几何题容易犯的错误
探花:中Tricks 探花:中Tricks 一般来说,计算几何题的题面都会有图, 所以读题不容易错.但是图也往往会有误 导性,会使我们的思维不全面,容易忽略 一些东西. 因此,在审题的时候千万要注意完整地思 考,不要因为有图就跳过题目中的重要条 件(虽然我常常这么做件(虽然我常常这么做-_-)

计算几何题容易犯的错误
榜眼:修改模版时改错 模版虽然牛,但是模版只能处理大概的情 况,很多题目对应的解题方法中模版需要 视情况改变.很多时候原本正确的模版, 在修改之后就出现了这样那样的问题. 千万不要想当然,修改也是做题的一部分, 一定要认真对待.

计算几何题容易犯的错误
状元!敲错变量 计算几何的代码量动辙上百行,而且抄写 占了很大一部分,查起来相当不容易.很 多时候一碗汤就是坏在一个i打成j 多时候一碗汤就是坏在一个i打成j的地方的. 写代码虽然要快,但是不出错才是最重要 的,100次罚时的AC也是AC,只有能 的,100次罚时的AC也是AC,只有能 AC了才需要考虑罚时! AC了才需要考虑罚时!

怎样训练计算几何题?
多做题,多写代码,不要怕麻烦 多读别人的代码(挑风格好的读,不要学 Topcoder),掌握快速发现问题的能力和 Topcoder),掌握快速发现问题的能力和 大方向上的思考能力 认真准备模版,确保自己有足够的能力应 付可能出现的修改. 培养良好的空间感觉 ……

That's all
Thank you!


推荐相关:
网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com