字:
关灯 护眼
网站首页 > 夜莺与神明[破鏡重圓] > 夜莺与神明[破鏡重圓] 第73节

夜莺与神明[破鏡重圓] 第73节(2 / 2)

而此刻,所有人的目光,都聚焦在了题板上那道依旧是灰色的、代表着无人解出的“j题”上——那是一道极其复杂的计算几何题。

(解题过程可选择跳过,不影响情节。)

题目背景:在一个二维平面上,分布着n个互不重叠的、由简单多边形代表的“居住区”(n可以高达10万)。现在,某科技公司计划发射m颗“通讯卫星”(m也可以高达10万),每颗卫星的信号覆盖范围都是一个完美的圆形。

题目要求:给出所有“居住区”的顶点坐标和m颗卫星的坐标及其信号半径。要求程序能够快速回答一个问题:对于每一颗卫星,它的信号完整覆盖了多少个“居住区”?

n和m都高达10万。如果采用最笨的办法——对于每一颗卫星,都去遍历所有n个居住区,并进行一次复杂的“完整覆盖”判定,那么总计算量将是m*n(即10万*10万=100亿次)。

竞赛计算机的单秒处理能力约1亿次,所以计算机处理时间是100秒,但是这时间远远超过了icpc题目通常给出的1-2秒的时间限制,而且这种解法没有技术含量,丢失了竞赛的意义。这个解法提交上去,得到的结果一定是“超时”(timelimitexceeded,简称tle),即解答失败。

这一道题的难点不在数学思想,而是如何在计算机的能力内在短时间内解决大规模数据,这只能从算法的角度去优化,在有限的计算机运算能力之下,高效完成任务。

程明笃的队友,现在都停下了手中的动作。

因为常规解法动辄需要上千代码量,这不是体力竞赛,必须要确定思路再行动才更加有效。

“首先不可能走时间复杂度这么高的方法,远远超时。”负责变成的队友神情有些焦灼,但是他们队伍呈现的状态还是较为稳定的。

程明笃作为队长,更是三人中最为平静的,他靠在椅背上,闭上了眼睛,手指在桌面上,无意识地、有节奏地轻轻敲击着。

那张清隽的脸上,没有丝毫的紧张,只有一种近乎冷酷的、绝对的专注。他仿佛已经抽离了这个嘈杂的赛场,进入了一个只有纯粹的算法世界。

突然,程明笃敲击的手指停住了。他睁开眼,那双总是深邃沉静的眼眸里,在那一瞬间,闪过了一道洞悉一切的、令人心悸的璀璨光芒。

他直接拿起白板笔,在旁边的小白板上,以一种快得惊人的速度,画出了一系列辅助线和几何模型,构建了一个所有人都没想到的、全新的坐标系。

“我们别再纠结‘面在不在圆里’,”他的笔尖在白板上飞舞,“问题的核心,是‘最远点’。我们要做一张‘查询地图’,把整个平面预先分割,而不是等查询来了再去计算。”

他首先运用“最远点voronoi图”的思想,为10万个“居住区”,各自生成了一张“谁离我最远”的答案地图。

他将这10万张地图叠加在一起,形成了一张包含了天文数字般信息的、极其复杂的“查询地图”。

运用“平面点定位算法”,为这张“查询地图”建立了一个查询引擎。

最后,当题目给出m颗卫星的坐标时,他们要做的,只是把每一颗卫星的坐标,一个一个地输入事先建立的“查询地图”里。

系统会瞬间告诉他,对于这颗卫星,1号居住区最远点是a,2号是b,3号是c……他们只需进行简单的距离判断,就能得出最终答案。

程明笃在白板上,用短短几十秒,清晰地勾勒出了这个堪称天马行空的、宏伟的算法框架。

他那两位同样是顶尖天才的队友,在最初的震惊过后,立刻领会了这个思路的精妙之处。

但紧接着,那个负责编码的队友,立刻指出了这个计划中最致命的、也是最现实的难题。

“思路很巧妙,但这个实现难度太高了!”他的神情凝重起来,“光是构建voronoi图时,计算那些由垂直平分线构成的交点,就会涉及大量的浮点数运算。double的精度误差是会累积的。只要有一个交点因为精度问题偏离了哪怕只偏离10^7,整个数据结构的拓扑关系就全错了,后面的所有查询,都会是垃圾结果。这道题的测试数据,一定是用最刁钻的方式,卡着我们精度的。”

这就是计算几何竞赛中的“魔鬼”——精度问题。它像一个幽灵,能让你明明拥有了全世界最正确的思路,却仍然写不出结果可接受的代码。

然而,程明笃似乎早就料到了这个问题。他的脸上,没有露出什么意外。

他拿起白板擦,擦掉了刚才画的一个辅助圆,然后看着两位队友,用一种异常冷静的语气说道:

“我知道。所以,我们不用double。”

队友愣住了:“不用double?那怎么计算交点和距离?”

“用我之前封装过一个几何库模板,所有的坐标点,我们全部用整型(longlong)来存储。所有涉及方向判定、点在线的哪一侧、内外关系等核心的几何判断,全部用基于向量的叉积和点积来计算。这样,我们就可以在整个建图过程中,从根本上避免任何浮点数的比较,保证所有拓扑关系的正确。”

“那距离呢?”数学队友追问,“最后一步判断‘最远点’和圆心的距离,必须要开方,一定会产生浮点数。”

“对,”程明笃点头,“但那已经是我们唯一需要动用浮点数的、最后一步了,但是我们不需要真的开方,用平方来进行比较,将精度误差的风险降低。”

题目上的沟壑,

如今他们用数学来一一填平。

程明笃负责在白板上,用他那强大的空间想象力,处理最复杂的逻辑和边界情况。

数学队友负责将程明笃的思路,转化为一行行严谨的数学推导,供编码的队友参考。

时间,来到最后一分钟。

“提交。”程明笃的声音此时已经掀不起一丝波澜。

对于真正能参加这场决赛的人来说,一道题得以巧妙解决,在出结果的瞬间就一直差不多知晓了。

队友按下提交键。全世界的目光,都聚焦在了他们队伍的屏幕上。

旋转,等待,判定……

当那个代表着“通过”的、绿色的“accepted”字样,在屏幕上亮起的瞬间——

全场响起了雷鸣般的掌声和惊呼声!

一个工作人员微笑着,拿着一只代表着“j题”的、独一无二的金色气球,走到了他们的座位旁,将它系好。

在整个赛场数百个五颜六色的气球中,这只金色的气球,如同胜利者加冕。

程明笃的队伍,在比赛结束前的最后几秒,成功解出了全场最难的一道题,几乎锁定了胜局!

颁奖礼上,主持人用激昂的声音,揭晓了那最后一小时的悬念,并最终喊出“20xx年icpc全球总决赛世界冠军——来自mit的‘infiniterecursion’队时,程明笃和他的队友们,在他二十岁不到的年纪,一起站上了那个属于全世界最聪明大脑的领奖台。

……

当晚,颁奖典礼结束后的酒店房间里,程明笃刚结束了和团队的庆祝。