tceic.com
学霸学习网 这下你爽了
相关标签
当前位置:首页 >> IT/计算机 >>

国家集训队2008论文集从立体几何问题看降低


从立体几何问题看降低编程复杂度

人大附中 高亦陶

引言:一类立体几何问题
O(1)的空间复杂度 O(1)的时间复杂度 并非公认的简单题

巨大的编程复杂度

1 运用合适的思维方式
使用方程是一种进步 方程是一种抽象的,通用的解题方法 但是方程有时会忽略一部分已知信息 通过具体地思考,充分利用已知信息可以 从本质入手,降低编程复杂度

例1 Model Rocket Height
给出两条直线的起点和方向,求它们公垂 线中点的高度. 直线方向用仰角和方向角表示.

数据的初步处理和思路
公垂线 叉积
n = a×b

方向向量

(1, tan α ,sec α tan θ )

尝试解题
uuu uuur uuur uuu r r AB = AD + DE BE

= λ1 a + λ3 n λ2 b

根据空间向量基本定理 有唯一解 可以化成 三元一次方程组 消元?行列式? 麻烦 浮点误差?

进一步思考
uuu uuur uuur uuu r r AB = AD + DE BE
uuu r uuur uuur AB n = DE n = DE n uuur uuu r uuur DE AB n DE = n = n 2 n n

另外两个未知量

uuur uuu uuur uuur uuu r r AB′ = AB DE = AD BE

三角形内已知一边和内角,求另一边长

最后一步
uuur uuur uuur AB′ b = PB′ b = PB′ b uuur uuur uuur PB′ AB′ b b = b PB′ = 2 b b uuur uuu r AD cos ∠DAP = AP uuur uuu r uuu 2 r uuu uuur uuur r AD AP uuur AP AP = AB′ PB′ uuu r r AD = a= a = uuu a a a AP a AP uuu a r a AP

小结
uuu r uuur AB n DE = n 2 n uuur uuu uuur r AB′ = AB DE uuur uuur AB′ b PB′ = b 2 b uuu uuur uuur r AP = AB′ PB′ uuu 2 r uuur AP r AD = uuu a a AP uuur uuu uuur 1 uuur r OC = OA + AD + DE 2

将盲目的方程组求解 改为一系列向量运算 降低了编程复杂度

2 注意分类讨论
大量的分类+复杂的判断=难以承受的编程 复杂度 合理地把不同的情况合并起来可以大大改 善这种状况

例2 Crossing Prisms
平面内有一个简单多 现在将这个多边形分 边形. 分别以这两个多边 别放置在xz面和yz面 形为底,以y轴和x 多边形边数≤4,每个 上.它们关于面x=y 轴为母线,以10为 顶点都是整点,坐标 对称. 高作两个棱柱. 取值范围为[0,10].顶 点按照逆时针方向排 求这两个棱柱的交 序. 的表面积.

关注表面
观察某个柱的一个侧面 它的一部分是交的表面

多数情况
如果侧面与底面不平行 交的表面一定是 用侧面截柱得到的截面 面积×cos二面角=射影面积 二面角很容易求 射影面积=柱底图形与y1 ≤ y ≤ y2的交的 面积

重要情况
如果侧面与底面平行 边数≤4 可以证明 只有图中两种情况

形状特殊的面

柱底图形 在特定高度上的宽 面积=宽2-(宽-边长)2

对正方形也适用!

继续利用这个宽

也可以用来计算射影面积! 射影面积=sum((宽1+宽2)*高/2) 需要对高度排序

算法框架
对高度排序 计算每点高度处的宽 枚举每一条边
判断平行与否 宽2-(宽-边长)2 或者 2*射影面积/cos二面角

计算宽 处理特殊情况
求所有边与y=yk的交点 最大值-最小值? ? 完全不考虑不规范交点? 利用逆时针顺序关系确定交点方向

面积≠(宽1+宽2)*高/2 ?
特判会打破先前的算法 框架 在局部改变宽的定义, 利用点的逆时针序忽略 一些边,使两个宽不同 修改两个点的高度顺序 最终使得面积可以照常计算

一种具体的处理办法
忽略和每个点相邻的边, 让凹角顶点对应的宽较 大 同时确保四个点的高按 逆时针顺序呈 1,2+,2-,3或3,2-,2+,1的 形式

小结:合并的效果
情况 判断 情况 情况 情况 判断 情况 情况 处理 中间量 比较复杂的计算途径 有点复杂的计算途径 另外的计算途径

另外的计算途径 剩下的计算途径

总结和启示
算法是多样化的,选择时要注重适用 适用性 适用 在遇到新问题时,首先想一想能不能在现 有框架内解决,而不是随意添加新的内容 对算法同样可以从类似内容中合并相同点 从而达到精简的效果

谢谢

推荐相关:

国家集训队2008论文集 pálya计数法的应用

国家集训队2008论文集 pálya计数法的应用_IT/计算机...为了理解 Pólya 计数 法,我们首先来看一下它所...把解决这类问题的时间 规模降到了一个非常低的水平...


noi论文分类

从立体几何问题看降低编程复杂度》 计算几何思想 2004 - 金恺:《极限法——...文档贡献者 天皇C罗 贡献于2016-08-16 1/2 相关文档推荐 NOI国家集训队论文...


国家集训队2008论文集浅谈最短路径问题中的

国家集训队2008论文集国家集训队2008论文集隐藏>> NOI Winter Camp 2008 浅谈最短径路问题中的分层思想福建省泉州市第七中学 吕子鉷 摘要分层思想与最短路径算法都...


国家集训队2008论文集浅谈信息学竞赛中的区

国家集训队2008论文集浅谈信息学竞赛中的区_IT/计算机..., f n 减小,即 li +1 , li + 2 ,…, ln...将每条旅行线路看做点.转化后的问题和 原问题完全...


国家集训队2008论文集浅析信息学竞赛中一类

国家集训队2008论文集国家集训队2008论文集隐藏>> 2008 年信息学奥领匹克竞赛冬令营论文 浙江 方戈 浅析信息学竞赛中一类与物理有关的问题杭州学军中学 方戈 摘要...


国家集训队2008论文集非完美算法初探——任

国家集训队2008论文集国家集训队2008论文集隐藏>> 非...下面我们来看一个使用抽样测试法的质数判断方法.对于...(7) T 逐渐减少,且 T->0,然后转第 2 步. ...


国家集训队2008论文集浅谈信息学中状态的合

请到百度文库投诉中心;如要提出功能问题或意见建议,...国家集训队2008论文集国家集训队2008论文集隐藏>> 浅谈...从而减少工作总时间,达到优化的 目的.从表面上看,...


国家集训队2008论文集部分贪心在信息学竞赛

国家集训队2008论文集国家集训队2008论文集隐藏>> 清华...——部分贪心 问题规模降低到较小的范围内以后,再...但是某些时候, 一些看上去十分正确而且效果明显的贪心...


国家集训队2008论文集 对块状链表的一点研

国家集训队2008论文集国家集训队2008论文集隐藏>> 对...大大降低了块状链表的效率,我们可以在每次操作后把...很明显,直接模拟就可以做,只不过不能 AC,而且看...


国家集训队1999论文集 邵铮

国家集训队1999论文集 周咏... 11页 免费 国家集训队2008论文集浅谈... 15...显然,一组 n-3 条互不相交的对角线对应于一种分割方案,因此可把问题看 作...

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