酷家乐2020校园招聘几何算法B卷这个题目标题我盯着看了很久。做家装设计软件的公司校招笔试里单独出一套几何算法卷子其实已经透露了很多信息几何相关的计算能力在这家公司的技术栈里不是“加分项”而是“必选项”。我自己搞了几年前端图形和CAD类算法也帮朋友辅导过不少图形学方向的校招笔试看到这类卷子首先感受到的不是“难度”而是“方向感”非常清晰——它就是奔着筛出真正能写计算几何代码的人去的。这篇内容不打算给你“背题”而是把这些年我带人准备这类笔试时最常用的一套思路整体梳理一遍酷家乐这类公司为什么考几何算法B卷的题目风格和考点通常集中在哪里每道高频考点的解题思路和代码长什么样以及最容易被忽视的实现细节。无论你是正在准备图形学、CAD、GIS方向校招的同学还是工作中突然要处理几何计算问题的工程师这篇都能给你一个相对完整的参考框架。1. 这场笔试到底在考什么从酷家乐的业务说开去很多人看到“酷家乐”第一反应是“装修效果图公司”然后就开始低估它技术笔试的含金量。实际上酷家乐的核心产品是云设计平台用户在里面画户型图、拖墙体、摆家具、做渲染你做的每一个操作背后几乎都在跑几何算法。1.1 为什么一家家装公司要考几何算法说得直白一点家装设计软件的底层就是一套几何引擎。你在界面上画一面墙程序需要判断这面墙和相邻墙是否相交交点在哪里你拖拽一个柜子程序需要检测它是否和另一件家具重叠你给房间封闭区域计算面积程序需要从一堆线段里提取出闭合多边形你渲染一张效果图模型在屏幕上的投影位置全靠几何变换。这些功能没有现成SDK能直接满足需求必须自己写几何计算代码。所以酷家乐的校招笔试把几何算法单独拎出来作为一卷本质上就是在问一个问题你能不能理解并实现几何计算的核心算法。B卷相对A卷来说通常考察点更偏计算几何的中等难度题型不要求你掌握特别顶级的论文级算法但很看重基础计算几何概念的熟练程度和代码实现的工程化能力。1.2 校招几何笔试题的三大考察维度我复盘过不少类似公司的几何方向笔试题发现无论是酷家乐、B站还是做CAD/CAE的厂商出的题目基本都落在三个维度上。第一是基础计算几何知识的掌握程度。点和向量的运算、叉积点积的几何意义、判断点与多边形的位置关系、判断线段相交、计算多边形面积、凸包算法等这些都是“默认你会”的内容。笔试题很少直接考“什么是叉积”这种概念题而是把概念藏在具体的场景题里比如“如何判断一个点是否在某个多边形房间内部”你写不出正确代码说明基本功不扎实。第二是工程化编码能力。笔试环境里没有IDE提示没有调试器的辅助有的平台有断点调试但时间紧张要求你在纯文本编辑器里写出一段能处理完整逻辑、覆盖边界条件的代码。很多同学算法思路没问题一写代码就暴露出循环边界写错、数组越界、浮点数比较用了等号等毛病。第三是时间和空间复杂度的意识。几何算法非常容易写出“正确但超时”的暴力解。比如最近点对问题两层for循环O(n²)一定能得出正确答案但在数据量达到十万级别时绝对超时。笔试不会明确告诉你“请用分治算法”它只给你一个数据范围让你自己去判断该用什么算法。1.3 B卷的整体难度定位我个人的判断是酷家乐这套B卷的整体难度大致介于“计算机考研数学基础题”和“ICPC区域赛计算几何入门题”之间。它不会出现三维凸包、Voronoi图、Delaunay三角剖分这类进阶内容但也不会只停留在“给你两个点求距离”这种入门水平。更像是一场“加难度的基础题测试”题目背景可能包装成户型绘制、空间布局、区域划分等业务场景但剥掉外衣后核心还是那几个经典计算几何问题。所以备战重点非常明确——把最常见的计算几何经典问题练熟远比盲目刷难题有用。2. 高频题型的拆解与应对思路这一节我把B卷里最常出现的题型逐一拆开讲每类题型都会给出解题思路和关键代码框架。这些都是我实际刷题、带人准备过程中反复验证过的高频点针对性非常强。2.1 向量基础与多边形判向很多题的隐藏起点向量运算在计算几何里就像小学里的四则运算几乎每道题都会用到。叉积尤其重要因为它的正负直接表示旋转方向。叉积的定义是a × b a.x * b.y - a.y * b.x。当结果大于0时说明向量b在向量a的逆时针方向结果小于0时说明b在a的顺时针方向等于0则共线。一个最经典的场景是判断点是否在多边形内部这几乎是酷家乐这类户型软件笔试的必考题。常见的做法有两种射线法和转角法。射线法的思路非常朴素从这个点引一条水平射线统计它与多边形边的交点个数。交点数为奇数点在多边形内交点数为偶数点在多边形外。这个方法实现起来容易忽略的细节有三个一是当射线恰好穿过多边形的顶点时如何处理二是当点恰好落在多边形边上时算不算内部三是水平边的处理。比较稳妥的做法是采用“射线法对顶点做特殊判断”的组合。我写过一个比较稳的Python实现def point_in_polygon(pt, poly): 射线法判断点是否在多边形内 pt: (x, y) 待判断点 poly: [(x1, y1), (x2, y2), ...] 多边形顶点按顺序排列 返回 True 表示在多边形内或在边上 x, y pt n len(poly) inside False for i in range(n): x1, y1 poly[i] x2, y2 poly[(i 1) % n] # 排除水平边和不与射线相交的边 if (y1 y) (y2 y): continue # 计算射线与边的交点横坐标 x_intersect (y - y1) * (x2 - x1) / (y2 - y1) x1 if x_intersect x: inside not inside return inside这个代码的关键在于“(y1 y) (y2 y)”这个判断它保证了顶点只在一条边上被计数一次避免奇数顶点被重复计算导致误判。另外要注意这个实现对于射线穿过顶点的情况是安全的但如果你要处理“点在边上”这个边界情况需要额外加线段跨立判断。转角法相比之下更复杂一些它通过计算多边形各个边相对于点的累计转角来判断点是否在多边形内部。如果累计转角为360度点在内部为0度点在外部。转角法的优势是不需要处理射线与顶点重合的特殊情况但代价是计算量更大且需要引入三角函数的反余弦精度上不如射线法可控。笔试里射线法通常够用了。实际在做户型判断的时候房间多边形可能是凹的也可能是带洞的如果题目没明确说明多边形类型需要先做好前置判断或者让代码天然支持凹多边形。上述射线法对凹多边形依然有效这是它比“面积法”更适合当通用解的原因。2.2 线段相交与矩形相交高频送分但容易出错线段相交判断在B卷里几乎每年都会出现通常被包装成“墙体是否碰撞”“管线是否交叉”等场景。判断两条线段是否相交标准做法是“快速排斥实验 跨立实验”。快速排斥实验的目的是排除明显不相交的情况如果两条线段的包围盒在x方向或y方向没有重叠那它们一定不相交。这个检查本身不充分但必要。跨立实验的核心是叉积。线段P1P2和Q1Q2相交的充要条件是P1和P2分别位于直线Q1Q2的两侧且Q1和Q2分别位于直线P1P2的两侧。用叉积表示就是def cross(a, b, c): # 向量ab与向量ac的叉积 return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0]) def seg_intersect(p1, p2, q1, q2): # 快速排斥 if max(p1[0], p2[0]) min(q1[0], q2[0]) or max(q1[0], q2[0]) min(p1[0], p2[0]): return False if max(p1[1], p2[1]) min(q1[1], q2[1]) or max(q1[1], q2[1]) min(p1[1], p2[1]): return False # 跨立实验 d1 cross(q1, q2, p1) d2 cross(q1, q2, p2) d3 cross(p1, p2, q1) d4 cross(p1, p2, q2) if d1 * d2 0 and d3 * d4 0: return True # 处理共线且重合的情况 if d1 0 and on_segment(q1, q2, p1): return True if d2 0 and on_segment(q1, q2, p2): return True if d3 0 and on_segment(p1, p2, q1): return True if d4 0 and on_segment(p1, p2, q2): return True return False这里最容易犯错的地方有两个。一是忘记快速排斥实验导致共线但分离的线段被误判为相交。二是只在叉积乘积小于0时返回True没有处理叉积等于0的共线情况共线线段端点是否落在对方线段上需要额外用on_segment函数判断。矩形相交判断相对简单常见的错误是直接用“顶点是否在对方矩形内”来判断两个矩形相交。这个思路对“完全不重叠”的情况有效但遗漏了“十字形交叉”的情况两个矩形既互相没有顶点在对方内部但它们确实有重叠区域。正确做法是把两个矩形的x方向投影和y方向投影分别拿来比较两者都有重叠才能判定矩形相交。2.3 凸包与极角排序校招笔试题的“必考题”凸包算是计算几何里最经典的算法之一也是酷家乐这类校招笔试的高频考点。它的应用场景在业务里很直观比如从一堆家具的顶点中计算出整个房间的可活动范围或者计算多个物体的外包络线。校招笔试里推荐用Andrew单调链算法求凸包因为相比之下Graham扫描法需要做极角排序而且起始点的选择和处理比较繁琐。Andrew算法的思路是先按x坐标排序x相同按y排序然后分别构造下凸链和上凸链。def cross(o, a, b): # 向量oa与ob的叉积 return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]) def convex_hull(points): points sorted(set(points)) if len(points) 1: return points lower [] for p in points: while len(lower) 2 and cross(lower[-2], lower[-1], p) 0: lower.pop() lower.append(p) upper [] for p in reversed(points): while len(upper) 2 and cross(upper[-2], upper[-1], p) 0: upper.pop() upper.append(p) return lower[:-1] upper[:-1]这里的要点在于当叉积小于等于0时出栈这样得到的凸包会排除共线点得到严格凸的结果。如果你希望凸包包含边上的点需要把条件改成小于0。笔试时如果题目没有特别要求一般排除共线点比较稳妥因为结果更简洁也方便后续处理。极角排序本身也是重要考点。按极角排序通常用两种方式一种是直接用atan2计算角度后排序优点是直观缺点是存在浮点误差且多次调用三角函数会比较慢另一种是用自定义比较函数通过叉积来判断两个向量的相对方向避免浮点计算。自定义比较的写法要注意叉积结果为0时说明两个向量共线此时应该按长度从小到大排序叉积为正说明向量a在向量b的逆时针方向a应该排在b前面。2.4 最近点对与平面划分从暴力到分治最近点对问题也是B卷中的常客。题目描述通常是给定平面上n个点求所有点对中距离最小的那一对。如果数据范围小直接暴力两层循环就能解决。但出题人通常会把n设置到10万级别逼迫你使用更优的算法。经典解法是分治法。把点按x坐标排序从中间划一条线分成左右两半分别递归求出左右两半的最短距离d。然后关键是处理“跨线”的情况只有距离中线距离小于d的点才可能有更短的距离而且这些点只需要和同侧y坐标距离小于d的点比较。按y坐标排序后对每个点只需检查后面的至多7个点。这个算法的复杂度是O(n log n)优化空间主要在合并阶段的常数。笔试实现时的常见失误是忘了对跨线区域的点按y坐标排序导致合并阶段复杂度退化到O(n²)。另一个容易被忽略的点是mid线附近可能存在大量横坐标相等的点这时候“距离中线小于d”的判断要写成“点横坐标减中线横坐标的绝对值小于d”而不是只看左右。写出来大概是这样的框架def closest_pair(points): # points 按 x 坐标排序 n len(points) if n 3: return brute_force(points) mid n // 2 mid_x points[mid][0] d min(closest_pair(points[:mid]), closest_pair(points[mid:])) strip [] for p in points: if abs(p[0] - mid_x) d: strip.append(p) strip.sort(keylambda p: p[1]) # 在strip中检查y轴距离小于d的相邻点 for i in range(len(strip)): j i 1 while j len(strip) and (strip[j][1] - strip[i][1]) d: d min(d, dist(strip[i], strip[j])) j 1 return d实际笔试中很多同学不会一上来就想到分治但至少应该能写出暴力解法。如果时间不够暴力解也能拿到部分分数。我在实际练习中发现分治算法的证明并不难但写代码时容易在“边界递归”上出错尤其是n为2和3时没有及时返回导致无限递归。建议在代码最开始就加上n3的暴力判断。3. 代码实现细节决定了你能不能拿分思路想清楚只是第一步。酷家乐这种公司出几何算法题重点考察的其实是你能不能把数学思路翻译成“能跑、能过边界用例”的工程代码。下面这几个实现细节是我反复经历过、也是笔试时最容易扣分的地方。3.1 浮点数判等的工程陷阱计算几何里绕不开浮点运算。叉积的结果可能是个很小的数比如1e-16它理论上应该是0但由于浮点精度问题计算出来不是0。如果用“ 0”来判断必然会出问题。正确的做法是引入一个极小量eps通常取1e-8或1e-10。判断叉积是否为零应该写为fabs(cross_value) eps。判断大于等于时也一样要写成cross_value -eps。不要小看这个细节。在在线评测系统里因为eps取不对导致精度不足而WAWrong Answer的代码要比因为算法思路错误而WA的还多。eps取多大不是固定的如果坐标范围很大eps可以适当取大一点如果题目要求高精度输出eps要慎重。一般取1e-8在多数题目里表现稳定。3.2 边界条件与退化情况几何算法最怕的不是复杂的常规情况而是各种“退化情况”点重合、线段退化成点、多边形边数为0、所有点共线、多边形是凹的、点在多边形边上等。一套完整的代码必须对这些边界情况给出明确合理的处理。比如前面讲到的点在多边形内的判断如果点恰好落在多边形的边上到底算内部还是外部这要看题目定义。有些题要求“边界也算内部”有些要求“只算内部不算边界”。如果题目没说明默认按“算内部”处理比较稳妥但最好在注释里写清楚你的处理方式。凸包算法里如果所有点共线Andrew算法会得到一条线段而不是一个凸多边形。这时候部分代码会因为没有处理“链上只有1个点”的情况而越界访问。这些边界情况一定要在编码时就想清楚别等测试数据帮你发现。3.3 时间复杂度的估算法别等超时才后悔笔试时一定要养成先看数据范围再决定算法的习惯。数据范围在1000以内O(n²)很安全n是10000O(n²)可能会卡时间n到100000必须想O(n log n)或更优的解法。我见过不少同学一上来就写暴力写了100行之后才发现n是十万。这时候就算改用正确的算法时间也浪费了。正确的做法是先花30秒看输入规模然后反向决定算法。比如要求“判断一个点是否在多个多边形内”如果多边形数量是10万点是1万那你最好预先对多边形做空间索引而不是逐一遍历。这类空间思维往往比单纯刷题更能体现一个工程师的素养。4. 调试技巧和笔试现场最容易踩的坑这部分我想换个角度不去罗列理论而是把我在实际刷题、模拟笔试时踩过的坑和总结出来的调试技巧直接写出来希望对你有直接帮助。4.1 用可视化辅助调试几何算法题的调试最痛苦的地方在于逻辑在脑子里转得过来但代码报错时你压根不知道是哪个几何关系判断错了。这时候我强烈建议用可视化辅助。如果你用的是本地IDE可以临时生成一份测试数据把点坐标、线段、多边形用matplotlib画出来然后对照代码结果和图形结果。笔试环境通常没有可视化工具那你就在纸上画。把关键的测试用例在纸上手动推演一遍再用代码跑一遍两者对照。这种习惯在准备阶段就应该养成。我平时刷计算几何题一定会先把样例的数据在草稿纸上画出来再写代码。这样不仅能降低调试时间还能在遇到“答案错误”时快速定位是哪个分支逻辑出了问题。4.2 随机数据对拍最朴素的正确性验证除了官方给的样例写一个简单的随机数据生成器再写一个暴力解作为基准然后用大规模随机数据对比暴力解和优化解的输出这种“对拍”方法在几何算法题里极其有效。比如你写了分治法的最近点对就写一个O(n²)的暴力解用随机生成的100组数据分别跑两个版本对比结果。如果某组数据不一致就缩小数据范围、用最小复现用例去定位bug。这个方法能帮你发现大量在样例里不可能暴露的问题。笔试时可能没有时间写对拍脚本但准备阶段如果养成习惯你写出来的代码bug率会大幅下降笔试时的通过率自然就高了。4.3 现场答题的时间分配建议我的建议是把时间分为三块前10分钟通读所有题目给每道题标注难度和预估时间中间60到80分钟集中攻克自己有把握的题按照“先易后难、先得分后优化”的原则最后留10到15分钟检查边界条件和代码语法。不要在一道难题上死磕。酷家乐这种校招笔试通常不止一个算法题而几何算法题往往一道比一道难。如果你在某道凸包题上卡了30分钟不如先去做后面的题目把能拿的分都拿到再回头攻难题。校招笔试不是竞赛排位赛只要你的总分够到面试线局部题目挂掉问题不大。另外代码风格和注释也很重要。虽然在线评测只看输出结果但有些笔试平台会人工审阅代码。思路清晰、变量命名规范、关键步骤有注释的代码会给你加分不少。这既是对你代码能力的体现也是对判卷人的尊重。5. 如何系统准备这类笔试“我刷了十道计算几何模板题能不能去考”、“需要啃《算法导论》几何章节吗”这类问题经常在我的交流群里出现。我的回答是刷题要刷但别无脑刷理论要读但别只读不写。准备工作应该分阶段推进。5.1 基础模板题的优先级排序第一优先级是点向量运算、线段相交、点在多边形内、多边形面积、凸包。这五个类型覆盖了酷家乐校招笔试绝大多数的基础题场景属于必须闭着眼能写出来的内容。第二优先级是最近点对分治法、极角排序、圆与圆/线与圆的相交判断、最大空矩形等稍进阶的问题。这些题目在B卷里出现的频率也不低但通常是给“区分度”用的。有时间就刷透没时间也要做到看题有思路。第三优先级是三维几何基础、半平面交、旋转卡壳、最小包围圆等冷门但偶尔出现的题型。这些不保证每年都考但如果你准备的岗位是渲染引擎或CAD底层面试时很可能会被问到。有时间准备总是好的。5.2 学习资料和练习路径的选择入门阶段我看的是《算法竞赛入门经典第二版》的计算几何章节里面对叉积、凸包的讲解非常直观而且代码风格适合竞赛。进阶一点的推荐《算法竞赛进阶指南》的几何部分里面有更多经典模型和推导过程适合把原理吃透。线上刷题的话力扣LeetCode有一些几何题但数量少且偏应用更适合用来热身真正的计算几何题集中在POJ、HDU、洛谷、Codeforces。建议每天固定刷1到2道几何题重点不是数量而是每道题都要理解透尽量做到“刷一道会一类”。5.3 知识复盘把题目反过来讲给自己听这是我学到的最有效的复盘方法。每做完一道几何题别急着看下一题先合上代码用口述的方式把这题的输入、输出、关键判断条件和边界情况讲给自己听。讲不通的地方往往就是你没理解透的地方。这个方法对计算几何尤其管用因为几何题最怕“感觉会了但写不出来”。你能讲清楚“叉积为什么能判断左右侧”、“凸包为什么用单调链能保证结果正确”说明你是真的掌握了核心逻辑。6. 我最后的几点体会关于这套“酷家乐2020校园招聘-几何算法B卷”我能给出的最直接的结论是它考察的不是天赋而是你在计算几何这条路上的刻意练习量。所有考点——叉积、射线法、凸包、分治法——都是公开的经典算法没有一个是需要“灵感”才能解出来的。你准备得好不好完全取决于是否把基础打牢、是否能把算法翻译成代码、是否在边界情况上踩过足够的坑。我个人在实际刷题和模拟笔试题时最深的体会是几何算法题的正确率和“浮点数处理习惯”高度正相关。一次把eps、边界条件、退化情况都想清楚提交一次就过的概率大约能提升一半。所以建议你在平时写代码时就把这些细节做成肌肉记忆。最后再分享一个小技巧如果你在校招笔试中遇到了一个毫无头绪的几何题不妨先从最简单的特殊情况入手把n1、n2、所有点都相同的用例在草稿纸上算一遍再从这些极简例子里反推规律。很多几何题的核心规律都是先从一个退化场景中悟出来的。祝准备笔试的朋友顺利上岸。
酷家乐2020校园招聘几何算法B卷这个题目标题我盯着看了很久。做家装设计软件的公司校招笔试里单独出一套几何算法卷子其实已经透露了很多信息几何相关的计算能力在这家公司的技术栈里不是“加分项”而是“必选项”。我自己搞了几年前端图形和CAD类算法也帮朋友辅导过不少图形学方向的校招笔试看到这类卷子首先感受到的不是“难度”而是“方向感”非常清晰——它就是奔着筛出真正能写计算几何代码的人去的。这篇内容不打算给你“背题”而是把这些年我带人准备这类笔试时最常用的一套思路整体梳理一遍酷家乐这类公司为什么考几何算法B卷的题目风格和考点通常集中在哪里每道高频考点的解题思路和代码长什么样以及最容易被忽视的实现细节。无论你是正在准备图形学、CAD、GIS方向校招的同学还是工作中突然要处理几何计算问题的工程师这篇都能给你一个相对完整的参考框架。1. 这场笔试到底在考什么从酷家乐的业务说开去很多人看到“酷家乐”第一反应是“装修效果图公司”然后就开始低估它技术笔试的含金量。实际上酷家乐的核心产品是云设计平台用户在里面画户型图、拖墙体、摆家具、做渲染你做的每一个操作背后几乎都在跑几何算法。1.1 为什么一家家装公司要考几何算法说得直白一点家装设计软件的底层就是一套几何引擎。你在界面上画一面墙程序需要判断这面墙和相邻墙是否相交交点在哪里你拖拽一个柜子程序需要检测它是否和另一件家具重叠你给房间封闭区域计算面积程序需要从一堆线段里提取出闭合多边形你渲染一张效果图模型在屏幕上的投影位置全靠几何变换。这些功能没有现成SDK能直接满足需求必须自己写几何计算代码。所以酷家乐的校招笔试把几何算法单独拎出来作为一卷本质上就是在问一个问题你能不能理解并实现几何计算的核心算法。B卷相对A卷来说通常考察点更偏计算几何的中等难度题型不要求你掌握特别顶级的论文级算法但很看重基础计算几何概念的熟练程度和代码实现的工程化能力。1.2 校招几何笔试题的三大考察维度我复盘过不少类似公司的几何方向笔试题发现无论是酷家乐、B站还是做CAD/CAE的厂商出的题目基本都落在三个维度上。第一是基础计算几何知识的掌握程度。点和向量的运算、叉积点积的几何意义、判断点与多边形的位置关系、判断线段相交、计算多边形面积、凸包算法等这些都是“默认你会”的内容。笔试题很少直接考“什么是叉积”这种概念题而是把概念藏在具体的场景题里比如“如何判断一个点是否在某个多边形房间内部”你写不出正确代码说明基本功不扎实。第二是工程化编码能力。笔试环境里没有IDE提示没有调试器的辅助有的平台有断点调试但时间紧张要求你在纯文本编辑器里写出一段能处理完整逻辑、覆盖边界条件的代码。很多同学算法思路没问题一写代码就暴露出循环边界写错、数组越界、浮点数比较用了等号等毛病。第三是时间和空间复杂度的意识。几何算法非常容易写出“正确但超时”的暴力解。比如最近点对问题两层for循环O(n²)一定能得出正确答案但在数据量达到十万级别时绝对超时。笔试不会明确告诉你“请用分治算法”它只给你一个数据范围让你自己去判断该用什么算法。1.3 B卷的整体难度定位我个人的判断是酷家乐这套B卷的整体难度大致介于“计算机考研数学基础题”和“ICPC区域赛计算几何入门题”之间。它不会出现三维凸包、Voronoi图、Delaunay三角剖分这类进阶内容但也不会只停留在“给你两个点求距离”这种入门水平。更像是一场“加难度的基础题测试”题目背景可能包装成户型绘制、空间布局、区域划分等业务场景但剥掉外衣后核心还是那几个经典计算几何问题。所以备战重点非常明确——把最常见的计算几何经典问题练熟远比盲目刷难题有用。2. 高频题型的拆解与应对思路这一节我把B卷里最常出现的题型逐一拆开讲每类题型都会给出解题思路和关键代码框架。这些都是我实际刷题、带人准备过程中反复验证过的高频点针对性非常强。2.1 向量基础与多边形判向很多题的隐藏起点向量运算在计算几何里就像小学里的四则运算几乎每道题都会用到。叉积尤其重要因为它的正负直接表示旋转方向。叉积的定义是a × b a.x * b.y - a.y * b.x。当结果大于0时说明向量b在向量a的逆时针方向结果小于0时说明b在a的顺时针方向等于0则共线。一个最经典的场景是判断点是否在多边形内部这几乎是酷家乐这类户型软件笔试的必考题。常见的做法有两种射线法和转角法。射线法的思路非常朴素从这个点引一条水平射线统计它与多边形边的交点个数。交点数为奇数点在多边形内交点数为偶数点在多边形外。这个方法实现起来容易忽略的细节有三个一是当射线恰好穿过多边形的顶点时如何处理二是当点恰好落在多边形边上时算不算内部三是水平边的处理。比较稳妥的做法是采用“射线法对顶点做特殊判断”的组合。我写过一个比较稳的Python实现def point_in_polygon(pt, poly): 射线法判断点是否在多边形内 pt: (x, y) 待判断点 poly: [(x1, y1), (x2, y2), ...] 多边形顶点按顺序排列 返回 True 表示在多边形内或在边上 x, y pt n len(poly) inside False for i in range(n): x1, y1 poly[i] x2, y2 poly[(i 1) % n] # 排除水平边和不与射线相交的边 if (y1 y) (y2 y): continue # 计算射线与边的交点横坐标 x_intersect (y - y1) * (x2 - x1) / (y2 - y1) x1 if x_intersect x: inside not inside return inside这个代码的关键在于“(y1 y) (y2 y)”这个判断它保证了顶点只在一条边上被计数一次避免奇数顶点被重复计算导致误判。另外要注意这个实现对于射线穿过顶点的情况是安全的但如果你要处理“点在边上”这个边界情况需要额外加线段跨立判断。转角法相比之下更复杂一些它通过计算多边形各个边相对于点的累计转角来判断点是否在多边形内部。如果累计转角为360度点在内部为0度点在外部。转角法的优势是不需要处理射线与顶点重合的特殊情况但代价是计算量更大且需要引入三角函数的反余弦精度上不如射线法可控。笔试里射线法通常够用了。实际在做户型判断的时候房间多边形可能是凹的也可能是带洞的如果题目没明确说明多边形类型需要先做好前置判断或者让代码天然支持凹多边形。上述射线法对凹多边形依然有效这是它比“面积法”更适合当通用解的原因。2.2 线段相交与矩形相交高频送分但容易出错线段相交判断在B卷里几乎每年都会出现通常被包装成“墙体是否碰撞”“管线是否交叉”等场景。判断两条线段是否相交标准做法是“快速排斥实验 跨立实验”。快速排斥实验的目的是排除明显不相交的情况如果两条线段的包围盒在x方向或y方向没有重叠那它们一定不相交。这个检查本身不充分但必要。跨立实验的核心是叉积。线段P1P2和Q1Q2相交的充要条件是P1和P2分别位于直线Q1Q2的两侧且Q1和Q2分别位于直线P1P2的两侧。用叉积表示就是def cross(a, b, c): # 向量ab与向量ac的叉积 return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0]) def seg_intersect(p1, p2, q1, q2): # 快速排斥 if max(p1[0], p2[0]) min(q1[0], q2[0]) or max(q1[0], q2[0]) min(p1[0], p2[0]): return False if max(p1[1], p2[1]) min(q1[1], q2[1]) or max(q1[1], q2[1]) min(p1[1], p2[1]): return False # 跨立实验 d1 cross(q1, q2, p1) d2 cross(q1, q2, p2) d3 cross(p1, p2, q1) d4 cross(p1, p2, q2) if d1 * d2 0 and d3 * d4 0: return True # 处理共线且重合的情况 if d1 0 and on_segment(q1, q2, p1): return True if d2 0 and on_segment(q1, q2, p2): return True if d3 0 and on_segment(p1, p2, q1): return True if d4 0 and on_segment(p1, p2, q2): return True return False这里最容易犯错的地方有两个。一是忘记快速排斥实验导致共线但分离的线段被误判为相交。二是只在叉积乘积小于0时返回True没有处理叉积等于0的共线情况共线线段端点是否落在对方线段上需要额外用on_segment函数判断。矩形相交判断相对简单常见的错误是直接用“顶点是否在对方矩形内”来判断两个矩形相交。这个思路对“完全不重叠”的情况有效但遗漏了“十字形交叉”的情况两个矩形既互相没有顶点在对方内部但它们确实有重叠区域。正确做法是把两个矩形的x方向投影和y方向投影分别拿来比较两者都有重叠才能判定矩形相交。2.3 凸包与极角排序校招笔试题的“必考题”凸包算是计算几何里最经典的算法之一也是酷家乐这类校招笔试的高频考点。它的应用场景在业务里很直观比如从一堆家具的顶点中计算出整个房间的可活动范围或者计算多个物体的外包络线。校招笔试里推荐用Andrew单调链算法求凸包因为相比之下Graham扫描法需要做极角排序而且起始点的选择和处理比较繁琐。Andrew算法的思路是先按x坐标排序x相同按y排序然后分别构造下凸链和上凸链。def cross(o, a, b): # 向量oa与ob的叉积 return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]) def convex_hull(points): points sorted(set(points)) if len(points) 1: return points lower [] for p in points: while len(lower) 2 and cross(lower[-2], lower[-1], p) 0: lower.pop() lower.append(p) upper [] for p in reversed(points): while len(upper) 2 and cross(upper[-2], upper[-1], p) 0: upper.pop() upper.append(p) return lower[:-1] upper[:-1]这里的要点在于当叉积小于等于0时出栈这样得到的凸包会排除共线点得到严格凸的结果。如果你希望凸包包含边上的点需要把条件改成小于0。笔试时如果题目没有特别要求一般排除共线点比较稳妥因为结果更简洁也方便后续处理。极角排序本身也是重要考点。按极角排序通常用两种方式一种是直接用atan2计算角度后排序优点是直观缺点是存在浮点误差且多次调用三角函数会比较慢另一种是用自定义比较函数通过叉积来判断两个向量的相对方向避免浮点计算。自定义比较的写法要注意叉积结果为0时说明两个向量共线此时应该按长度从小到大排序叉积为正说明向量a在向量b的逆时针方向a应该排在b前面。2.4 最近点对与平面划分从暴力到分治最近点对问题也是B卷中的常客。题目描述通常是给定平面上n个点求所有点对中距离最小的那一对。如果数据范围小直接暴力两层循环就能解决。但出题人通常会把n设置到10万级别逼迫你使用更优的算法。经典解法是分治法。把点按x坐标排序从中间划一条线分成左右两半分别递归求出左右两半的最短距离d。然后关键是处理“跨线”的情况只有距离中线距离小于d的点才可能有更短的距离而且这些点只需要和同侧y坐标距离小于d的点比较。按y坐标排序后对每个点只需检查后面的至多7个点。这个算法的复杂度是O(n log n)优化空间主要在合并阶段的常数。笔试实现时的常见失误是忘了对跨线区域的点按y坐标排序导致合并阶段复杂度退化到O(n²)。另一个容易被忽略的点是mid线附近可能存在大量横坐标相等的点这时候“距离中线小于d”的判断要写成“点横坐标减中线横坐标的绝对值小于d”而不是只看左右。写出来大概是这样的框架def closest_pair(points): # points 按 x 坐标排序 n len(points) if n 3: return brute_force(points) mid n // 2 mid_x points[mid][0] d min(closest_pair(points[:mid]), closest_pair(points[mid:])) strip [] for p in points: if abs(p[0] - mid_x) d: strip.append(p) strip.sort(keylambda p: p[1]) # 在strip中检查y轴距离小于d的相邻点 for i in range(len(strip)): j i 1 while j len(strip) and (strip[j][1] - strip[i][1]) d: d min(d, dist(strip[i], strip[j])) j 1 return d实际笔试中很多同学不会一上来就想到分治但至少应该能写出暴力解法。如果时间不够暴力解也能拿到部分分数。我在实际练习中发现分治算法的证明并不难但写代码时容易在“边界递归”上出错尤其是n为2和3时没有及时返回导致无限递归。建议在代码最开始就加上n3的暴力判断。3. 代码实现细节决定了你能不能拿分思路想清楚只是第一步。酷家乐这种公司出几何算法题重点考察的其实是你能不能把数学思路翻译成“能跑、能过边界用例”的工程代码。下面这几个实现细节是我反复经历过、也是笔试时最容易扣分的地方。3.1 浮点数判等的工程陷阱计算几何里绕不开浮点运算。叉积的结果可能是个很小的数比如1e-16它理论上应该是0但由于浮点精度问题计算出来不是0。如果用“ 0”来判断必然会出问题。正确的做法是引入一个极小量eps通常取1e-8或1e-10。判断叉积是否为零应该写为fabs(cross_value) eps。判断大于等于时也一样要写成cross_value -eps。不要小看这个细节。在在线评测系统里因为eps取不对导致精度不足而WAWrong Answer的代码要比因为算法思路错误而WA的还多。eps取多大不是固定的如果坐标范围很大eps可以适当取大一点如果题目要求高精度输出eps要慎重。一般取1e-8在多数题目里表现稳定。3.2 边界条件与退化情况几何算法最怕的不是复杂的常规情况而是各种“退化情况”点重合、线段退化成点、多边形边数为0、所有点共线、多边形是凹的、点在多边形边上等。一套完整的代码必须对这些边界情况给出明确合理的处理。比如前面讲到的点在多边形内的判断如果点恰好落在多边形的边上到底算内部还是外部这要看题目定义。有些题要求“边界也算内部”有些要求“只算内部不算边界”。如果题目没说明默认按“算内部”处理比较稳妥但最好在注释里写清楚你的处理方式。凸包算法里如果所有点共线Andrew算法会得到一条线段而不是一个凸多边形。这时候部分代码会因为没有处理“链上只有1个点”的情况而越界访问。这些边界情况一定要在编码时就想清楚别等测试数据帮你发现。3.3 时间复杂度的估算法别等超时才后悔笔试时一定要养成先看数据范围再决定算法的习惯。数据范围在1000以内O(n²)很安全n是10000O(n²)可能会卡时间n到100000必须想O(n log n)或更优的解法。我见过不少同学一上来就写暴力写了100行之后才发现n是十万。这时候就算改用正确的算法时间也浪费了。正确的做法是先花30秒看输入规模然后反向决定算法。比如要求“判断一个点是否在多个多边形内”如果多边形数量是10万点是1万那你最好预先对多边形做空间索引而不是逐一遍历。这类空间思维往往比单纯刷题更能体现一个工程师的素养。4. 调试技巧和笔试现场最容易踩的坑这部分我想换个角度不去罗列理论而是把我在实际刷题、模拟笔试时踩过的坑和总结出来的调试技巧直接写出来希望对你有直接帮助。4.1 用可视化辅助调试几何算法题的调试最痛苦的地方在于逻辑在脑子里转得过来但代码报错时你压根不知道是哪个几何关系判断错了。这时候我强烈建议用可视化辅助。如果你用的是本地IDE可以临时生成一份测试数据把点坐标、线段、多边形用matplotlib画出来然后对照代码结果和图形结果。笔试环境通常没有可视化工具那你就在纸上画。把关键的测试用例在纸上手动推演一遍再用代码跑一遍两者对照。这种习惯在准备阶段就应该养成。我平时刷计算几何题一定会先把样例的数据在草稿纸上画出来再写代码。这样不仅能降低调试时间还能在遇到“答案错误”时快速定位是哪个分支逻辑出了问题。4.2 随机数据对拍最朴素的正确性验证除了官方给的样例写一个简单的随机数据生成器再写一个暴力解作为基准然后用大规模随机数据对比暴力解和优化解的输出这种“对拍”方法在几何算法题里极其有效。比如你写了分治法的最近点对就写一个O(n²)的暴力解用随机生成的100组数据分别跑两个版本对比结果。如果某组数据不一致就缩小数据范围、用最小复现用例去定位bug。这个方法能帮你发现大量在样例里不可能暴露的问题。笔试时可能没有时间写对拍脚本但准备阶段如果养成习惯你写出来的代码bug率会大幅下降笔试时的通过率自然就高了。4.3 现场答题的时间分配建议我的建议是把时间分为三块前10分钟通读所有题目给每道题标注难度和预估时间中间60到80分钟集中攻克自己有把握的题按照“先易后难、先得分后优化”的原则最后留10到15分钟检查边界条件和代码语法。不要在一道难题上死磕。酷家乐这种校招笔试通常不止一个算法题而几何算法题往往一道比一道难。如果你在某道凸包题上卡了30分钟不如先去做后面的题目把能拿的分都拿到再回头攻难题。校招笔试不是竞赛排位赛只要你的总分够到面试线局部题目挂掉问题不大。另外代码风格和注释也很重要。虽然在线评测只看输出结果但有些笔试平台会人工审阅代码。思路清晰、变量命名规范、关键步骤有注释的代码会给你加分不少。这既是对你代码能力的体现也是对判卷人的尊重。5. 如何系统准备这类笔试“我刷了十道计算几何模板题能不能去考”、“需要啃《算法导论》几何章节吗”这类问题经常在我的交流群里出现。我的回答是刷题要刷但别无脑刷理论要读但别只读不写。准备工作应该分阶段推进。5.1 基础模板题的优先级排序第一优先级是点向量运算、线段相交、点在多边形内、多边形面积、凸包。这五个类型覆盖了酷家乐校招笔试绝大多数的基础题场景属于必须闭着眼能写出来的内容。第二优先级是最近点对分治法、极角排序、圆与圆/线与圆的相交判断、最大空矩形等稍进阶的问题。这些题目在B卷里出现的频率也不低但通常是给“区分度”用的。有时间就刷透没时间也要做到看题有思路。第三优先级是三维几何基础、半平面交、旋转卡壳、最小包围圆等冷门但偶尔出现的题型。这些不保证每年都考但如果你准备的岗位是渲染引擎或CAD底层面试时很可能会被问到。有时间准备总是好的。5.2 学习资料和练习路径的选择入门阶段我看的是《算法竞赛入门经典第二版》的计算几何章节里面对叉积、凸包的讲解非常直观而且代码风格适合竞赛。进阶一点的推荐《算法竞赛进阶指南》的几何部分里面有更多经典模型和推导过程适合把原理吃透。线上刷题的话力扣LeetCode有一些几何题但数量少且偏应用更适合用来热身真正的计算几何题集中在POJ、HDU、洛谷、Codeforces。建议每天固定刷1到2道几何题重点不是数量而是每道题都要理解透尽量做到“刷一道会一类”。5.3 知识复盘把题目反过来讲给自己听这是我学到的最有效的复盘方法。每做完一道几何题别急着看下一题先合上代码用口述的方式把这题的输入、输出、关键判断条件和边界情况讲给自己听。讲不通的地方往往就是你没理解透的地方。这个方法对计算几何尤其管用因为几何题最怕“感觉会了但写不出来”。你能讲清楚“叉积为什么能判断左右侧”、“凸包为什么用单调链能保证结果正确”说明你是真的掌握了核心逻辑。6. 我最后的几点体会关于这套“酷家乐2020校园招聘-几何算法B卷”我能给出的最直接的结论是它考察的不是天赋而是你在计算几何这条路上的刻意练习量。所有考点——叉积、射线法、凸包、分治法——都是公开的经典算法没有一个是需要“灵感”才能解出来的。你准备得好不好完全取决于是否把基础打牢、是否能把算法翻译成代码、是否在边界情况上踩过足够的坑。我个人在实际刷题和模拟笔试题时最深的体会是几何算法题的正确率和“浮点数处理习惯”高度正相关。一次把eps、边界条件、退化情况都想清楚提交一次就过的概率大约能提升一半。所以建议你在平时写代码时就把这些细节做成肌肉记忆。最后再分享一个小技巧如果你在校招笔试中遇到了一个毫无头绪的几何题不妨先从最简单的特殊情况入手把n1、n2、所有点都相同的用例在草稿纸上算一遍再从这些极简例子里反推规律。很多几何题的核心规律都是先从一个退化场景中悟出来的。祝准备笔试的朋友顺利上岸。
![[光学原理与应用-521]：对光的错误理解与纠偏](http://pic.xiahunao.cn/yaotu/[光学原理与应用-521]：对光的错误理解与纠偏)
