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论文集从立体几何问题看降低_图文.ppt

国家集训队2008论文集从立体几何问题看降低 - 从立体几何问题看降低编程复杂度


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

国家集训队2008论文集浅谈最短路径问题中的_IT/...计算几何中判断点是否在多边形中的方法是:从 点引出...利用分层的性质,就可以减少冗余, 使之降低甚至接近...


国家集训队2008论文集 计算几何中的二分思.doc

国家集训队2008论文集 计算几何中的二分思 - 计算几何中的二分思想 计算几何中的二分思想 二分 贵阳市第一中学 程祺 【摘要】 摘要】 本文简要阐述了...


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

国家集训队2008论文集浅谈信息学中状态的合 - 浅谈信息学中状态的合理设计与应


国家集训队2008论文集浅谈随机化思想在几何_图文.ppt

国家集训队2008论文集浅谈随机化思想在几何 - 感受随机的美 浅谈随机化思想在几何问题中的应用 广东中山一中 顾研 引入 随着信息学的发展,近几年,各种各样...


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

国家集训队2008论文集部分贪心在信息学竞赛 - 清华附中 高逸涵 部分贪心思想


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

国家集训队2008论文集 对块状链表的一点研_IT/...很明显,直接模拟就可以


国家集训队2008论文集 论文.pdf

国家集训队2008论文集 论文 - 运用化归思想解决信息学中的数列问题 余林韵


中国国家集训队论文集目录(1999-2009).txt

国家集训队2008论文集 Day1 1.曹钦翔《数据结构的提炼与压缩》 2.郑暾《平衡...数列问题》 7.任一恒《非完美算法初探》 8.高亦陶《从立体几何问题看降低编程...


国家集训队2008论文集余林韵_运用化归思想_图文.ppt

国家集训队2008论文集余林韵_运用化归思想 - 福建省福州市第一中学 余林韵


国家集训队论文分类整理.pdf

国家集训队论文分类整理来源: 洪雁书的日志距离 NOI 时间越来越少了,选择性地...《长方体体积并》 2008 - 高亦陶《从立体几何问题看降低编程复杂度》 2004 -...


NOI国家集训队论文分类(至2008)(摘抄自C博客).doc

NOI国家集训队论文分类(至2008)(摘抄自C博客)_学科竞赛_高中教育_教育专区。...《从立体几何问题看降低编程复杂度》 计算几何思想 2004 - 金恺:《极限法...


国家集训队论文分类.xls

2008 2005 2002 2002 2005 2006 2007 2005 2008 2003 2004 - 高亦陶《从立体几何问题看降低编程复杂度》 金恺:《极限法解决几何最优化问题的捷径》 程...


目录.txt

国家集训队2008论文集 Day1 1.曹钦翔《数据结构的提炼与压缩》 2.郑暾《平衡...数列问题》 7.任一恒《非完美算法初探》 8.高亦陶《从立体几何问题看降低编程...


content.txt

国家集训队2008论文集 Day1 1.曹钦翔《数据结构的提炼与压缩》 2.郑暾《平衡...数列问题》 7.任一恒《非完美算法初探》 8.高亦陶《从立体几何问题看降低编程...


noi论文分类.doc

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


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

国家集训队2008论文集浅析信息学竞赛中一类 - 浅析信息学竞赛中 一类与物理有关的问题 杭州学军中学 方戈 序言 看上去简单 ?贴近实际 ?实现方法多 ?易转化...


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

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


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

国家集训队2008论文集非完美算法初探任 - 非完美算法的应用 河北唐山一中 任一恒 在平时的练习和考试中,我们都是尽量设计出完全正确的算法来解决问 题....


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

国家集训队2008论文集部分贪心在信息学竞赛 - 部分贪心在信息学竞赛中的应用

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