Posted on 2010-06-23 00:08
王之昊 阅读(510)
评论(1) 编辑 收藏 引用 所属分类:
三维几何 、
分类讨论 、
intricate
题意: 给一个正八面体，有只蚂蚁要从面上一点走到另一点，只能沿表面走，求最短距离。
为了讨论方便,首先给所有顶点标号,如图所示.
分四类讨论：
1)共面情况( 两点都在面ABC上 )
两点之间直线最短, 这时直接计算两点之间距离
2)相邻面情况(一点在面ABC上, 一点在面ACD上 )
最短路径只可能是两个相邻面摊开的直线距离,如图所示:
其他路径可以反射到这两个面上证明他们不是最优的.例如:
红线路径和黄线路径是等价的,而红线路径显然没有前一幅图的蓝线路径优.
3)同在上侧的“对立面”情况( 一点在面ABC上, 一点在面ADE上 ).
最优情况有两种:
- 从 面ABC 到 面ACD 到 面ADE
- 从 面ABC 到 面ABE 到 面ADE
同2)一样利用反射的方法可以证明其他走法不是最优的.
4)严格“对面”情况(一点在面ABC上, 一点在面DEF上 )。
枚举所有可能的六种情况.
其他的情况都可以通过坐标变换转化成这四种情况