20多年前一个晚上,10点半了,电话铃响起,是一位非常要好的朋友打来的。他在修计算机课,一个回家作业明天要交,实在想不出,就想到了我。 一个多边形(N条边),凹凸不限。同一平面有一个点,可以在多边形内部,也可以在外部。从该点画一射线,哪一个方向穿透的“边”最多,有几条。现在要求用计算机程序完成这个过程。 下面两行“***”之间,与(简单)数学有关,不感兴趣的读者可跳过。 *** 稍作思考,我就想到了方法。令该点为原点,将多边形各点用极坐标写出,要求角度在0° 和360° 之间。将相邻点配对,共 N 对。在每一对中,如果起始角度大于终止角度,就将两点互换,这样保证了每一对中,第二个角大于第一个角。 将N个角度排序,将从小到大的N个区间(不是N条边对应的区间)逐个检验,看包含了多少对(部分或全部),大部分情况只包含了一条边对应的角度的一部分。唯一的麻烦是包含了x 正轴的那个区间。我们只要检验,在现在的坐标体系,有多少条边跨越了x 正轴。 *** 第二段中的检验过程,很可能并非最佳选择,还有更好的方法。但这时已经半夜12点多了,不管白猫黑猫,先把老鼠抓住再说。我事后问他,为什么隔天晚上这么晚才打电话,不早点来问。他说,不好意思打搅我,走投无路了才给我打电话!真是哭笑不得。 20多年过去,此事已逐渐淡忘。退休后,我家买了一辆 Lexus。一辆车一般寿命10年,太太说,我们也没几个10年了,应该享受一下了。 买车时,推销员使出浑身解数,先进功能介绍了一样又一样,真是此车只能天上有。其中有一项功能是开门关门不用钥匙,只要在车子的某几个部位之一摸一下就可以了。当然这是有前提的,钥匙不能太远,女士们一般把钥匙放在手提包内,自然就满足要求了。 几天前,太太发现车门没法关,换了我的手去摸,也是不行。忽然她想起,这次钥匙没有放在包里,在驾驶座边上。钥匙拿出来,再关就可以了。这个设计确实不错,钥匙不会忘在车里。推销员口若悬河的时候忘了吹。 车子怎么知道我没把钥匙带出来?我想到了20多年前的枪手经历。可以在车子的四个角装四个感应器,四条边可以看作是四面墙壁,一个简单程序只要判断钥匙是否在“墙“内就可以了。
|