前几天一个学弟找我聊天说拿到了酷家乐校招的笔试邀请点开链接一看题目明晃晃写着“几何算法B卷”整个人有点懵。他说自己刷了不少常规算法题链表、动态规划、二叉树都见过唯独几何这块准备得最少一上考场看到向量、射线、多边形相交这些字眼心态先崩了一半。这种感受我太熟悉了——自己当年参加校招时也栽过类似的跟头。后来工作后接触了云设计软件背后的渲染、建模、户型识别系统才真正理解为什么像酷家乐这样的公司会把几何算法当成校招笔试的核心考察点。这篇就借“酷家乐2020校园招聘-几何算法B卷”这个话题把这类题目背后的考察逻辑、高频题型的推导思路、考场实战注意点一次性讲透。无论你是准备投酷家乐还是瞄准其他做图形、CAD、云渲染方向的岗位这篇文章的内容都能直接拿来用。1. 为什么云设计公司校招笔试会重点考几何算法很多人看到“几何算法”四个字第一反应是这是大学《计算几何》课本里的冷门内容和日常开发没什么关系。但如果你了解酷家乐这种云设计平台的产品形态就会明白几何算法不是选做题而是整个技术体系的基石。1.1 几何算法在云设计软件里的真实用途酷家乐的核心场景是让用户在线完成户型绘制、硬装软装布置、效果图渲染。一个用户从画出第一面墙开始到最终生成一份可落地的设计方案背后几乎每一步都跑着几何计算。画户型时墙线需要自动闭合生成房间拖拽家具时模型碰撞需要精确判断材质铺贴时要计算纹理坐标与多边形区域的关系渲染输出时相机视锥体裁剪、光照采样、遮挡剔除更是大量依赖球体、平面、三角形网格之间的几何关系。这还只是最直观的几个场景。再往后走比如一键自动布局、智能样板间生成、水电管线自动排布这些功能的本质都是在二维或三维空间里做几何约束求解。理解了这个背景你就能看懂笔试题目为什么会出线段相交、点在多边形内、凸包计算这一类问题——它们不是凭空想出来的而是直接映射到真实产品功能里的基础模块。校招笔试不可能让你写一整套渲染引擎但完全可以用一道几何算法题考察你是否有能力理解和实现这些基础模块。1.2 B卷的考察定位与背后意图从笔试分卷这个细节来看B卷通常对应的是图形、几何、渲染方向的技术岗位和通用的A卷算法题会有明显差异。通用算法卷考察的是数据结构和思维严密性几何算法卷则在此基础上额外考察三个维度的能力数学基础是否扎实、空间想象力是否够用、代码实现是否能处理工程级的边缘条件。我接触过不少候选人聊起来都知道凸包有什么算法纸上推导也能写两步但一落到实际编码就露馅了。比如判断线段相交只考虑“规范相交”而遗漏了“共线重叠”的情况比如射线法判断点在多边形内时没有处理射线过顶点导致的奇偶性判断失效再比如浮点数比较直接用“”几轮计算之后误差累积直接把结果带偏。这些细节恰恰是笔试判分的关键点也是面试官想通过题目看到的东西。他们不指望你写出教科书里那种精简但脆弱的实现而是希望看到你对边界情况的完整处理。2. 几何算法B卷中的高频考点与核心推导那一年酷家乐B卷具体考了哪些题不同批次和年份会有差异但高频核心考点的分布是非常稳定的。我把方向上最常出现的几类问题拆开来讲从原理到推导再到代码实现一条线走完。2.1 向量叉积与线段相交判定向量叉积是计算几何最基础的工具也是笔试里几乎必考的知识点。两个二维向量a(x1, y1)和b(x2, y2)的叉积定义为x1y2 - y1x2几何意义是由这两个向量构成的平行四边形的有向面积。叉积的正负可以用来判断两个向量的相对方向叉积为正说明b在a的逆时针方向为负说明在顺时针方向为零说明共线。线段相交判定问题本质上就是利用叉积的方向性。给定两条线段P1P2和Q1Q2先做快速排斥实验也就是判断以两条线段为对角线的矩形是否相交。如果矩形都不相交线段肯定不相交这一步可以快速排除大部分情况。快速排斥通过后再做跨立实验判断P1P2的两个端点是否分别位于Q1Q2所在直线的两侧同时Q1Q2的两个端点是否分别位于P1P2所在直线的两侧。用叉积表达就是计算(cross(Q1, Q2, P1) * cross(Q1, Q2, P2) 0)和(cross(P1, P2, Q1) * cross(P1, P2, Q2) 0)是否同时成立。等号处理的是端点落在另一条线段上的情况也就是非规范相交。这个判定方法笔试时一定要写对因为它是后面很多题目的基础。规范相交的写法是去掉等号只需要判断严格在两侧。但实际工程里绝大多数情况需要把端点相触、共线重叠也判定为相交所以等号不能丢。我建议你把这个模板背熟实现时单独封装一个函数笔试时能省出不少时间。2.2 点在多边形内的射线法判断一个点是否在任意多边形内部是户型识别、区域选择、碰撞检测里逃不开的问题。笔试中出现的多边形一般是简单多边形也就是边不交叉的多边形。射线法的基本思路是从待判断的点向任意方向发出一条射线统计这条射线与多边形边的交点数量。如果有奇数个交点点在多边形内部偶数个交点在外部。这个方法的直觉解释是从内部点发出的射线穿过多边形边界时每穿一次就在内外部之间切换一次。射线法的实现比听起来要复杂难点在特殊情况的处理上。交点正好经过多边形的顶点时怎么算射线和多边形某条边共线时怎么办如果这些情况不处理奇偶性判断就会出错结果时对时错但笔试样例很难覆盖这类刁钻的边界。业界主流做法是“半开区间”策略也就是统计边时只统计边的上端点不统计下端点。具体实现细节是对于每条边i-i1只有当点的y坐标位于两个端点y值之间时才进行跨立测试如果某个端点恰好等于点的y坐标则统一按上端点或下端点来处理。这种约定能有效避免重复计数。另一种从“半开区间”角度思考的做法是将边缘情况定义为点在边界上并提前单独判断是否落在边的范围内如果落在边界上直接返回真。笔试时建议两者结合先遍历所有边判断点是否在线段上再做射线法统计。虽然多了一个循环但逻辑更清晰不容易被边界case卡住。2.3 凸包计算与极值求解凸包问题同样是几何算法卷的高频题它要求求出包含平面点集的最小凸多边形。笔试中凸包问题的意义有两个层面第一它直接考察你对几何排序和单调栈的理解第二它经常作为更复杂问题的前置步骤比如求最小外接矩形、计算点集直径、做碰撞体积估计等。常见的凸包算法有Gift Wrapping卷包裹法和Andrew单调链算法。卷包裹法的思路是从最左下角的点出发每次找一个点使得所有剩余点都在当前边的同一侧直到回到起点复杂度为O(nh)h是凸包顶点数。Andrew算法则是先按x坐标排序再分别构造下凸包和上凸包整体复杂度为O(nlogn)是笔试和工程里更推荐的方案。Andrew算法的核心代码逻辑是维护一个栈遍历排序后的点集在加入新点时判断栈顶三个点是否构成逆时针方向。如果方向不对就弹栈直到满足凸性条件。判断方向依然用叉积。这个算法理解起来比卷包裹法稍微抽象一点但好在代码短、思路直背熟模板后在笔试里很容易快速写对。2.4 数值稳定性与浮点误差处理笔试时的测试数据通常是整数坐标误差问题不明显。但如果你写的是浮点版本或者题目样例里混合了浮点坐标那误差处理就会决定你能否通过全部测试用例。计算几何里最典型的误差陷阱是直接使用等号比较浮点数。两个浮点数经过各自不同的运算路径即使理论上相等在二进制表示里也可能差出最后一比特。处理方式一般是定义一个极小值eps比如1e-9或1e-10。判断叉积是否为0时不写cross 0而是写fabs(cross) eps。判断两个点是否相等时不写x1 x2 y1 y2而是写fabs(x1 - x2) eps fabs(y1 - y2) eps。这样处理之后程序对微小的舍入误差就有了容忍度。但要注意eps也不宜设得过大否则会把本来不相邻的几何元素误判成重叠。笔试时统一用1e-9基本不会出问题。还有一点是关于整数坐标的。有的题目从输入数据上就能保证所有坐标都是整数此时尽量用整数运算避免用浮点数。整数型叉积不仅不会有精度问题而且计算速度更快。只有当题目明确要求输出浮点结果或者原始输入本来就有浮点数时才需要引入eps体系。3. 拿到这类题目后的考场破题顺序笔试现场的时间有限几何算法题又偏偏是那种容易让人陷进去的类型。我自己的经验是拿到题目后先不要急着写代码按固定节奏走普遍能比直接上手编码多拿不少分。3.1 先把题目条件翻译成几何语言很多几何算法题的原始描述并不像算法题更像一个业务场景故事。比如“请判断一扇门是否能够在这个墙洞内完全打开”翻译过来可能就是一个多边形旋转后是否与障碍物相交的问题。第一步就是抛开故事背景把输入、输出和约束条件用纯粹的几何概念重写一遍。这个过程中需要重点确认的信息包括坐标系是二维还是三维坐标范围有多大数值是整数还是浮点数多边形的边是否存在自交点是否可能落在线段上或者多边形边界上要求返回布尔值还是计算具体交点坐标。这些细节直接决定你选择哪套模板和边界处理策略。很多时候考场上并不是你不会写算法而是没有发现题目条件里暗含的坑。比如有些题目会说明“所有点坐标均为整数且互不相同”那你的eps处理就可以简化甚至完全用整数运算。我在模拟笔试时发现一个现象大部分人在时间紧张的情况下会在题目条件还没读清楚前就急急忙忙打开编辑器。结果写了一半才发现以为输入是一个多边形实际是一组散点以为要判断点是否在多边形里实际是判断多边形自身是否自交。这些错误一旦发生返工的时间成本极高。所以第一步花五分钟做翻译和确认性价比非常高。3.2 先写主流程再补边界条件确定好题目条件后建议先搭主流程骨架。以点在多边形内为例主流程就是遍历所有边统计射线交点返回奇偶性结果。先把这段核心代码写出来确认基础逻辑跑通再回到边缘case逐条补充。这样做的好处是至少保证你拿到基础分。很多笔试系统是按测试用例比例给分的主干逻辑正确就能通过百分之六七十的用例边界问题导致剩下百分之三四十失败。如果你一上来就纠结边界条件可能主流程还没跑通时间就到了。反之先把最简单的完整方案写对再逐步打补丁最后一定能拿到相当不错的分数。补边界条件时我的常用检查顺序是有没有点在多边形边界上射线是否经过顶点射线是否与边共线两条线段是否恰好首尾相接。这四类情况基本覆盖了计算几何笔试题里大部分的隐藏case。我在笔试和后来的日常编码中都把这个检查清单固化成肌肉记忆很管用。4. 从笔试题目到工程实现的常见坑位笔试题目写得再漂亮终究和工程实战有距离。但反过来如果在笔试阶段就能避免掉进工程级的大坑说明你是真有几何算法的感觉。下面这几个坑是我自己在实际开发里踩过的也是校招笔试里最容易试探候选人的点。4.1 只考虑凸多边形而忽略凹多边形很多人在学校里练几何题时接触的多边形大多是凸的比如三角形、矩形、正五边形。因此做点在多边形内或者多边形相交判断时代码里隐藏地假设了多边形是凸的。射线法对凹多边形是天然有效的因为它只依赖奇偶性统计不需要凸性假设。但如果你用“转角法”或“叉积方向一致法”来判断点在多边形内就会在凹多边形上直接翻车因为这些方法默认多边形是凸的。笔试题目里如果出现“多边形”这个词一定要多留一个心眼确认题目明说它是凸多边形还是普通简单多边形。虽然一般题目不会太阴险但你不能赌它是凸的。射线法虽然实现要小心边界条件但它不挑多边形形状是最稳妥的选择。4.2 坐标系方向与顺时针/逆时针的混淆二维坐标系里x轴向右、y轴向上是数学里的常见约定但在屏幕绘制和图像处理场景里y轴往往向下。这道题使用的是数学坐标系还是屏幕坐标系会直接影响叉积正负对应的视觉含义。如果你靠直觉判断“叉积为正代表点在直线左侧”再碰到y轴向下的场景就会左右颠倒出bug。笔试时如果输入数据自己无法确定坐标系不妨手画几个简单样例跑一遍验证结果是否符合直觉。比如一个点明显在一条有向线段的右边看程序输出是左还是右和你肉眼判断的是否一致。如果题目附带了样例直接用样例验证这是最稳的。另外判断多边形顶点给出的顺序是顺时针还是逆时针也会影响面积计算和方向判断类题目的正负号。建议在代码开头写一个函数计算多边形有向面积符号为负说明是顺时针为正说明是逆时针后续方向判断需要时直接调用。4.3 使用O(n^2)暴力法时不注意数据范围还有些几何题表面是让你计算最优方案但数据范围小得离谱比如散点只有几百个这时候完全可以直接写暴力法。反过来也有一种情况题目范围看着不大但几何运算常数因子很高O(n^2)算法跑起来比预期慢得多。所以做题前看清楚约束范围数据量允许时老老实实写暴力省下时间去优化其他题往往比在几何题上强行抠一个复杂度更优算法划算。我在笔试题里见过有的候选人明明n只有200非要去写一个复杂度低但要调试很久的扫描线优化算法结果代码没调通基础暴力分也没拿全。笔试不是比赛拿分才是核心目标。几何算法题更是如此能按题目数据范围选最简单合适的解法本身就是工程能力的体现。5. 复盘“几何算法B卷”的备考路线如果你正在准备类似酷家乐这样的公司校招笔试最后这部分内容是给你直接抄作业的路线图。我从知识储备、刷题策略、临场心态三个角度整理了一份可执行的建议。5.1 打好计算几何的核心知识基础计算几何的题库不像通用算法题那么庞大核心知识点相对集中优先掌握这些就足够应对大多数笔试二维向量与坐标系基础、叉积与点积的几何意义、线段相交判定、点在多边形内判定、凸包计算、多边形面积计算、最小外接矩形或最近点对扩展。这些知识点之间是层叠关系向量叉积是地基线段相交和点含多边形是中层凸包和面积是应用层。建议按这个顺序学每层掌握后再进下一层稳扎稳打。理论学习之外务必把手写代码的能力练到位。看懂了和写对了之间隔着大量的边缘case。我的做法是每学一个算法就在自己的代码环境里徒手实现一遍不参考模板像考试一样限时完成。第一次写会比较痛苦但写过两三遍后基本可以盲写出来。到了考场上即使是紧张状态肌肉记忆也能帮你把核心模板写对。5.2 刷题方向与时间分配刷题时建议优先刷计算几何专项题库而非散落在综合题库里的几何题。常见的OJ平台上有专门的几何分类按难度从入门到进阶刷一刷。刷题数量上不求多但求每道题都吃透。一道线段相交的题目做完后想一想如果改成线段与矩形相交怎么处理如果改成判断多边形是否自交呢这种举一反三的思考方式比题海战术效率高得多。时间分配上几何算法题的调试点往往比较隐蔽建议笔试时每道题预留至少二十分钟纯调试时间。如果你的整体笔试时间是一个半小时三到四道题的情况下几何题最多占四十分钟不能在局部花太久否则后面的题没有时间保障。我习惯的顺序是先把所有题目快速审一遍优先做自己最有把握的题几何题放在中间段位既不耽误刚开场的状态也有充足的时间处理复杂边界条件。5.3 面试官在纸面上寻找什么站在面试官视角重新看这套笔试卷子你会发现他们要捕捉的信号远不止“答对答案”那么简单。几何算法题之所以被挑出来作为笔试区分度最高的题型是因为它天然具备三层观察窗口第一层看基础编码能力能否把思路落实成结构清晰的代码第二层看数学抽象能力能否把业务描述翻译成精确的几何定义第三层看工程素养能否主动处理浮点误差、边界情况、鲁棒性等矛盾。如果你在答卷的适当位置写下简短注释说明你在处理哪种边界条件这在面试官眼里是很大的加分项。比如在射线法代码旁边注释一行“经过顶点时按上端点计”面试官翻卷子时能快速捕捉到你的思考深度。这一点在后续面试中也会成为聊下去的话题点所以笔试答卷不要只写代码关键的思考痕迹要留一点。按这个思路准备下来再看到“几何算法B卷”这种标题时你就不会心里发怵了。它考察的东西其实很实在——扎实的数学功底、熟练的代码手感外加一点工程上的谨慎。把这三点练到位无论遇到哪家公司的几何算法题你都能稳住节奏把该拿的分拿到手。我后来带团队面试时也常拿这类题当试金石真正能写出高质量几何代码的人在渲染、建模这类复杂系统里大概率也是靠谱的。 
长河君 · 2026/8/29 5:10:25 · 阅读 1.2k 酷家乐几何算法B卷：从向量叉积到凸包的校招笔试攻略
前几天一个学弟找我聊天说拿到了酷家乐校招的笔试邀请点开链接一看题目明晃晃写着“几何算法B卷”整个人有点懵。他说自己刷了不少常规算法题链表、动态规划、二叉树都见过唯独几何这块准备得最少一上考场看到向量、射线、多边形相交这些字眼心态先崩了一半。这种感受我太熟悉了——自己当年参加校招时也栽过类似的跟头。后来工作后接触了云设计软件背后的渲染、建模、户型识别系统才真正理解为什么像酷家乐这样的公司会把几何算法当成校招笔试的核心考察点。这篇就借“酷家乐2020校园招聘-几何算法B卷”这个话题把这类题目背后的考察逻辑、高频题型的推导思路、考场实战注意点一次性讲透。无论你是准备投酷家乐还是瞄准其他做图形、CAD、云渲染方向的岗位这篇文章的内容都能直接拿来用。1. 为什么云设计公司校招笔试会重点考几何算法很多人看到“几何算法”四个字第一反应是这是大学《计算几何》课本里的冷门内容和日常开发没什么关系。但如果你了解酷家乐这种云设计平台的产品形态就会明白几何算法不是选做题而是整个技术体系的基石。1.1 几何算法在云设计软件里的真实用途酷家乐的核心场景是让用户在线完成户型绘制、硬装软装布置、效果图渲染。一个用户从画出第一面墙开始到最终生成一份可落地的设计方案背后几乎每一步都跑着几何计算。画户型时墙线需要自动闭合生成房间拖拽家具时模型碰撞需要精确判断材质铺贴时要计算纹理坐标与多边形区域的关系渲染输出时相机视锥体裁剪、光照采样、遮挡剔除更是大量依赖球体、平面、三角形网格之间的几何关系。这还只是最直观的几个场景。再往后走比如一键自动布局、智能样板间生成、水电管线自动排布这些功能的本质都是在二维或三维空间里做几何约束求解。理解了这个背景你就能看懂笔试题目为什么会出线段相交、点在多边形内、凸包计算这一类问题——它们不是凭空想出来的而是直接映射到真实产品功能里的基础模块。校招笔试不可能让你写一整套渲染引擎但完全可以用一道几何算法题考察你是否有能力理解和实现这些基础模块。1.2 B卷的考察定位与背后意图从笔试分卷这个细节来看B卷通常对应的是图形、几何、渲染方向的技术岗位和通用的A卷算法题会有明显差异。通用算法卷考察的是数据结构和思维严密性几何算法卷则在此基础上额外考察三个维度的能力数学基础是否扎实、空间想象力是否够用、代码实现是否能处理工程级的边缘条件。我接触过不少候选人聊起来都知道凸包有什么算法纸上推导也能写两步但一落到实际编码就露馅了。比如判断线段相交只考虑“规范相交”而遗漏了“共线重叠”的情况比如射线法判断点在多边形内时没有处理射线过顶点导致的奇偶性判断失效再比如浮点数比较直接用“”几轮计算之后误差累积直接把结果带偏。这些细节恰恰是笔试判分的关键点也是面试官想通过题目看到的东西。他们不指望你写出教科书里那种精简但脆弱的实现而是希望看到你对边界情况的完整处理。2. 几何算法B卷中的高频考点与核心推导那一年酷家乐B卷具体考了哪些题不同批次和年份会有差异但高频核心考点的分布是非常稳定的。我把方向上最常出现的几类问题拆开来讲从原理到推导再到代码实现一条线走完。2.1 向量叉积与线段相交判定向量叉积是计算几何最基础的工具也是笔试里几乎必考的知识点。两个二维向量a(x1, y1)和b(x2, y2)的叉积定义为x1y2 - y1x2几何意义是由这两个向量构成的平行四边形的有向面积。叉积的正负可以用来判断两个向量的相对方向叉积为正说明b在a的逆时针方向为负说明在顺时针方向为零说明共线。线段相交判定问题本质上就是利用叉积的方向性。给定两条线段P1P2和Q1Q2先做快速排斥实验也就是判断以两条线段为对角线的矩形是否相交。如果矩形都不相交线段肯定不相交这一步可以快速排除大部分情况。快速排斥通过后再做跨立实验判断P1P2的两个端点是否分别位于Q1Q2所在直线的两侧同时Q1Q2的两个端点是否分别位于P1P2所在直线的两侧。用叉积表达就是计算(cross(Q1, Q2, P1) * cross(Q1, Q2, P2) 0)和(cross(P1, P2, Q1) * cross(P1, P2, Q2) 0)是否同时成立。等号处理的是端点落在另一条线段上的情况也就是非规范相交。这个判定方法笔试时一定要写对因为它是后面很多题目的基础。规范相交的写法是去掉等号只需要判断严格在两侧。但实际工程里绝大多数情况需要把端点相触、共线重叠也判定为相交所以等号不能丢。我建议你把这个模板背熟实现时单独封装一个函数笔试时能省出不少时间。2.2 点在多边形内的射线法判断一个点是否在任意多边形内部是户型识别、区域选择、碰撞检测里逃不开的问题。笔试中出现的多边形一般是简单多边形也就是边不交叉的多边形。射线法的基本思路是从待判断的点向任意方向发出一条射线统计这条射线与多边形边的交点数量。如果有奇数个交点点在多边形内部偶数个交点在外部。这个方法的直觉解释是从内部点发出的射线穿过多边形边界时每穿一次就在内外部之间切换一次。射线法的实现比听起来要复杂难点在特殊情况的处理上。交点正好经过多边形的顶点时怎么算射线和多边形某条边共线时怎么办如果这些情况不处理奇偶性判断就会出错结果时对时错但笔试样例很难覆盖这类刁钻的边界。业界主流做法是“半开区间”策略也就是统计边时只统计边的上端点不统计下端点。具体实现细节是对于每条边i-i1只有当点的y坐标位于两个端点y值之间时才进行跨立测试如果某个端点恰好等于点的y坐标则统一按上端点或下端点来处理。这种约定能有效避免重复计数。另一种从“半开区间”角度思考的做法是将边缘情况定义为点在边界上并提前单独判断是否落在边的范围内如果落在边界上直接返回真。笔试时建议两者结合先遍历所有边判断点是否在线段上再做射线法统计。虽然多了一个循环但逻辑更清晰不容易被边界case卡住。2.3 凸包计算与极值求解凸包问题同样是几何算法卷的高频题它要求求出包含平面点集的最小凸多边形。笔试中凸包问题的意义有两个层面第一它直接考察你对几何排序和单调栈的理解第二它经常作为更复杂问题的前置步骤比如求最小外接矩形、计算点集直径、做碰撞体积估计等。常见的凸包算法有Gift Wrapping卷包裹法和Andrew单调链算法。卷包裹法的思路是从最左下角的点出发每次找一个点使得所有剩余点都在当前边的同一侧直到回到起点复杂度为O(nh)h是凸包顶点数。Andrew算法则是先按x坐标排序再分别构造下凸包和上凸包整体复杂度为O(nlogn)是笔试和工程里更推荐的方案。Andrew算法的核心代码逻辑是维护一个栈遍历排序后的点集在加入新点时判断栈顶三个点是否构成逆时针方向。如果方向不对就弹栈直到满足凸性条件。判断方向依然用叉积。这个算法理解起来比卷包裹法稍微抽象一点但好在代码短、思路直背熟模板后在笔试里很容易快速写对。2.4 数值稳定性与浮点误差处理笔试时的测试数据通常是整数坐标误差问题不明显。但如果你写的是浮点版本或者题目样例里混合了浮点坐标那误差处理就会决定你能否通过全部测试用例。计算几何里最典型的误差陷阱是直接使用等号比较浮点数。两个浮点数经过各自不同的运算路径即使理论上相等在二进制表示里也可能差出最后一比特。处理方式一般是定义一个极小值eps比如1e-9或1e-10。判断叉积是否为0时不写cross 0而是写fabs(cross) eps。判断两个点是否相等时不写x1 x2 y1 y2而是写fabs(x1 - x2) eps fabs(y1 - y2) eps。这样处理之后程序对微小的舍入误差就有了容忍度。但要注意eps也不宜设得过大否则会把本来不相邻的几何元素误判成重叠。笔试时统一用1e-9基本不会出问题。还有一点是关于整数坐标的。有的题目从输入数据上就能保证所有坐标都是整数此时尽量用整数运算避免用浮点数。整数型叉积不仅不会有精度问题而且计算速度更快。只有当题目明确要求输出浮点结果或者原始输入本来就有浮点数时才需要引入eps体系。3. 拿到这类题目后的考场破题顺序笔试现场的时间有限几何算法题又偏偏是那种容易让人陷进去的类型。我自己的经验是拿到题目后先不要急着写代码按固定节奏走普遍能比直接上手编码多拿不少分。3.1 先把题目条件翻译成几何语言很多几何算法题的原始描述并不像算法题更像一个业务场景故事。比如“请判断一扇门是否能够在这个墙洞内完全打开”翻译过来可能就是一个多边形旋转后是否与障碍物相交的问题。第一步就是抛开故事背景把输入、输出和约束条件用纯粹的几何概念重写一遍。这个过程中需要重点确认的信息包括坐标系是二维还是三维坐标范围有多大数值是整数还是浮点数多边形的边是否存在自交点是否可能落在线段上或者多边形边界上要求返回布尔值还是计算具体交点坐标。这些细节直接决定你选择哪套模板和边界处理策略。很多时候考场上并不是你不会写算法而是没有发现题目条件里暗含的坑。比如有些题目会说明“所有点坐标均为整数且互不相同”那你的eps处理就可以简化甚至完全用整数运算。我在模拟笔试时发现一个现象大部分人在时间紧张的情况下会在题目条件还没读清楚前就急急忙忙打开编辑器。结果写了一半才发现以为输入是一个多边形实际是一组散点以为要判断点是否在多边形里实际是判断多边形自身是否自交。这些错误一旦发生返工的时间成本极高。所以第一步花五分钟做翻译和确认性价比非常高。3.2 先写主流程再补边界条件确定好题目条件后建议先搭主流程骨架。以点在多边形内为例主流程就是遍历所有边统计射线交点返回奇偶性结果。先把这段核心代码写出来确认基础逻辑跑通再回到边缘case逐条补充。这样做的好处是至少保证你拿到基础分。很多笔试系统是按测试用例比例给分的主干逻辑正确就能通过百分之六七十的用例边界问题导致剩下百分之三四十失败。如果你一上来就纠结边界条件可能主流程还没跑通时间就到了。反之先把最简单的完整方案写对再逐步打补丁最后一定能拿到相当不错的分数。补边界条件时我的常用检查顺序是有没有点在多边形边界上射线是否经过顶点射线是否与边共线两条线段是否恰好首尾相接。这四类情况基本覆盖了计算几何笔试题里大部分的隐藏case。我在笔试和后来的日常编码中都把这个检查清单固化成肌肉记忆很管用。4. 从笔试题目到工程实现的常见坑位笔试题目写得再漂亮终究和工程实战有距离。但反过来如果在笔试阶段就能避免掉进工程级的大坑说明你是真有几何算法的感觉。下面这几个坑是我自己在实际开发里踩过的也是校招笔试里最容易试探候选人的点。4.1 只考虑凸多边形而忽略凹多边形很多人在学校里练几何题时接触的多边形大多是凸的比如三角形、矩形、正五边形。因此做点在多边形内或者多边形相交判断时代码里隐藏地假设了多边形是凸的。射线法对凹多边形是天然有效的因为它只依赖奇偶性统计不需要凸性假设。但如果你用“转角法”或“叉积方向一致法”来判断点在多边形内就会在凹多边形上直接翻车因为这些方法默认多边形是凸的。笔试题目里如果出现“多边形”这个词一定要多留一个心眼确认题目明说它是凸多边形还是普通简单多边形。虽然一般题目不会太阴险但你不能赌它是凸的。射线法虽然实现要小心边界条件但它不挑多边形形状是最稳妥的选择。4.2 坐标系方向与顺时针/逆时针的混淆二维坐标系里x轴向右、y轴向上是数学里的常见约定但在屏幕绘制和图像处理场景里y轴往往向下。这道题使用的是数学坐标系还是屏幕坐标系会直接影响叉积正负对应的视觉含义。如果你靠直觉判断“叉积为正代表点在直线左侧”再碰到y轴向下的场景就会左右颠倒出bug。笔试时如果输入数据自己无法确定坐标系不妨手画几个简单样例跑一遍验证结果是否符合直觉。比如一个点明显在一条有向线段的右边看程序输出是左还是右和你肉眼判断的是否一致。如果题目附带了样例直接用样例验证这是最稳的。另外判断多边形顶点给出的顺序是顺时针还是逆时针也会影响面积计算和方向判断类题目的正负号。建议在代码开头写一个函数计算多边形有向面积符号为负说明是顺时针为正说明是逆时针后续方向判断需要时直接调用。4.3 使用O(n^2)暴力法时不注意数据范围还有些几何题表面是让你计算最优方案但数据范围小得离谱比如散点只有几百个这时候完全可以直接写暴力法。反过来也有一种情况题目范围看着不大但几何运算常数因子很高O(n^2)算法跑起来比预期慢得多。所以做题前看清楚约束范围数据量允许时老老实实写暴力省下时间去优化其他题往往比在几何题上强行抠一个复杂度更优算法划算。我在笔试题里见过有的候选人明明n只有200非要去写一个复杂度低但要调试很久的扫描线优化算法结果代码没调通基础暴力分也没拿全。笔试不是比赛拿分才是核心目标。几何算法题更是如此能按题目数据范围选最简单合适的解法本身就是工程能力的体现。5. 复盘“几何算法B卷”的备考路线如果你正在准备类似酷家乐这样的公司校招笔试最后这部分内容是给你直接抄作业的路线图。我从知识储备、刷题策略、临场心态三个角度整理了一份可执行的建议。5.1 打好计算几何的核心知识基础计算几何的题库不像通用算法题那么庞大核心知识点相对集中优先掌握这些就足够应对大多数笔试二维向量与坐标系基础、叉积与点积的几何意义、线段相交判定、点在多边形内判定、凸包计算、多边形面积计算、最小外接矩形或最近点对扩展。这些知识点之间是层叠关系向量叉积是地基线段相交和点含多边形是中层凸包和面积是应用层。建议按这个顺序学每层掌握后再进下一层稳扎稳打。理论学习之外务必把手写代码的能力练到位。看懂了和写对了之间隔着大量的边缘case。我的做法是每学一个算法就在自己的代码环境里徒手实现一遍不参考模板像考试一样限时完成。第一次写会比较痛苦但写过两三遍后基本可以盲写出来。到了考场上即使是紧张状态肌肉记忆也能帮你把核心模板写对。5.2 刷题方向与时间分配刷题时建议优先刷计算几何专项题库而非散落在综合题库里的几何题。常见的OJ平台上有专门的几何分类按难度从入门到进阶刷一刷。刷题数量上不求多但求每道题都吃透。一道线段相交的题目做完后想一想如果改成线段与矩形相交怎么处理如果改成判断多边形是否自交呢这种举一反三的思考方式比题海战术效率高得多。时间分配上几何算法题的调试点往往比较隐蔽建议笔试时每道题预留至少二十分钟纯调试时间。如果你的整体笔试时间是一个半小时三到四道题的情况下几何题最多占四十分钟不能在局部花太久否则后面的题没有时间保障。我习惯的顺序是先把所有题目快速审一遍优先做自己最有把握的题几何题放在中间段位既不耽误刚开场的状态也有充足的时间处理复杂边界条件。5.3 面试官在纸面上寻找什么站在面试官视角重新看这套笔试卷子你会发现他们要捕捉的信号远不止“答对答案”那么简单。几何算法题之所以被挑出来作为笔试区分度最高的题型是因为它天然具备三层观察窗口第一层看基础编码能力能否把思路落实成结构清晰的代码第二层看数学抽象能力能否把业务描述翻译成精确的几何定义第三层看工程素养能否主动处理浮点误差、边界情况、鲁棒性等矛盾。如果你在答卷的适当位置写下简短注释说明你在处理哪种边界条件这在面试官眼里是很大的加分项。比如在射线法代码旁边注释一行“经过顶点时按上端点计”面试官翻卷子时能快速捕捉到你的思考深度。这一点在后续面试中也会成为聊下去的话题点所以笔试答卷不要只写代码关键的思考痕迹要留一点。按这个思路准备下来再看到“几何算法B卷”这种标题时你就不会心里发怵了。它考察的东西其实很实在——扎实的数学功底、熟练的代码手感外加一点工程上的谨慎。把这三点练到位无论遇到哪家公司的几何算法题你都能稳住节奏把该拿的分拿到手。我后来带团队面试时也常拿这类题当试金石真正能写出高质量几何代码的人在渲染、建模这类复杂系统里大概率也是靠谱的。