《从立体几何问题看降低编程复杂度》由会员分享，可在线阅读，更多相关《从立体几何问题看降低编程复杂度（24页珍藏版）》请在金锄头文库上搜索。
1、从立体几何问题看降低编程复杂度人大附中 高亦陶引言：一类立体几何问题lO(1)的空间复杂度lO(1)的时间复杂度l并非公认的简单题巨大的编程复杂度1 运用合适的思维方式l使用方程是一种进步 方程是一种抽象的、通用的解题方法 但是方程有时会忽略一部分已知信息l通过具体地思考、充分利用已知信息可以 从本质入手，降低编程复杂度例1 Model Rocket Heightl给出两条直线的起点和方向，求它们公垂 线中点的高度。l直线方向用仰角和方向角表示。数据的初步处理和思路公垂线叉积方向向量消元？行列式？ 浮点误差？根据空间向量基本定理 有唯一解尝试解题可以化成 三元一次方程组麻烦进一步思考另外两个未
2、知量三角形内已知一边和内角，求另一边长最后一步小结将盲目的方程组求解 改为一系列向量运算降低了编程复杂度2 注意分类讨论l大量的分类+复杂的判断=难以承受的编程 复杂度l合理地把不同的情况合并起来可以大大改 善这种状况例2 Crossing Prismsl平面内有一个简单多 边形。l多边形边数4，每个 顶点都是整点，坐标 取值范围为0,10。顶 点按照逆时针方向排 序。l现在将这个多边形分 别放置在xz面和yz面 上。它们关于面xy 对称。l分别以这两个多边 形为底，以y轴和x 轴为母线，以10为 高作两个棱柱。l求这两个棱柱的交 的表面积。关注表面观察某个柱的一个侧面它的一部分是交的表面多数
3、情况如果侧面与底面不平行交的表面一定是 用侧面截柱得到的截面面积cos二面角射影面积二面角很容易求射影面积柱底图形与y1 y y2的交的 面积重要情况如果侧面与底面平行边数4可以证明 只有图中两种情况形状特殊的面柱底图形 在特定高度上的宽面积宽2-(宽-边长)2对正方形也适用！继续利用这个宽也可以用来计算射影面积！射影面积sum(宽1+宽2)*高/2)需要对高度排序算法框架l对高度排序l计算每点高度处的宽l枚举每一条边判断平行与否宽2-(宽-边长)2或者2*射影面积/cos二面角计算宽 处理特殊情况求所有边与y=yk的交点最大值-最小值?完全不考虑不规范交点?利用逆时针顺序关系确定交点方向面积
4、(宽1+宽2)*高/2 ?在局部改变宽的定义， 利用点的逆时针序忽略 一些边，使两个宽不同修改两个点的高度顺序 最终使得面积可以照常计算特判会打破先前的算法 框架一种具体的处理办法忽略和每个点相邻的边 ，让凹角顶点对应的宽 较大同时确保四个点的高按 逆时针顺序呈 1,2+,2-,3或3,2-,2+,1的 形式小结：合并的效果情况情况情况判断比较复杂的计算途径有点复杂的计算途径另外的计算途径判断情况情况情况处理中间量另外的计算途径剩下的计算途径总结和启示l算法是多样化的，选择时要注重适用性l在遇到新问题时，首先想一想能不能在现 有框架内解决，而不是随意添加新的内容l对算法同样可以从类似内容中合并相同点 从而达到精简的效果谢谢
